You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

In the mythical land of the Alphabetical Kingdom, there exists a vast network of cities connected by enchanted roads. Each city is represented by a letter of the English alphabet, making the kingdom's structure closely tied to the language of letters. The kingdom's ruler, the wise King Mr. Heart, is very particular about the letters in his kingdom and seeks to understand the most dominant letter in any given part of his realm.

The kingdom consists of N cities (nodes), and each city has a single letter S associated with it. The cities are connected by N-1 enchanted roads (edges) that ensure all cities are accessible from any other, forming a vast network with no cycles—a true tree structure. Mr. Heart lives in the capital city of this kingdom, which is nodes 1 (this is the root nodes of each cities).

The King has Q questions about his kingdom. For each query, he will give you two types of query :

• 1 K C - you have to update the node K with the charater C.
• 2 K - your task is to determine which letter is the most frequent among the cities under the administration of that city K ( subtree of this k), including the city itself. If there is a tie in frequency, the lexicographically smaller letter should be chosen.
  
  According to this tree, node 2, which is in charge of nodes 3, 4, 5, and 6. Conversely, node 4 is in charge of nodes 5 and 6. However, All of the nodes are under the control of node 1.

Input

First Line N (1 ≤ N ≤ \(10^5\)), the number of city.
Second Line, which contains N small english letter S and separated by space.
Next N - 1 Lines each contains two integers U and V which means there has a road between city U and V.
The next line which contains Q (1 ≤ Q ≤ \(10^5\)), the number of Query.
Each query takes two types of input in the following format

• 1 K C
• 2 K

K(1 ≤ K ≤ N), a specific node(city) of the kingdom and C , which is contains small english latter.

Output

Print the most frequent value (lexically small one) in each query.

Sample

7
a d b c a a c
1 2
1 3
3 4
3 5
3 7
5 6
5
2 1
2 3
1 5 b
2 3
2 2

a
a
b
d