Tree Keyboard

Dr. PCK has developed a revolutionary input device for computers, the Tree Keyboard. This keyboard has $N$ keys, each numbered $1$ to $N$, and they are wired with $N-1$ wires. You can also reach other keys by following some wires from any key.

As a keyboard setting, each key can be assigned a single character, and these can be changed at will at any time. On this keyboard, when you press a key $s$ and then a key $t$, the characters of all the keys on the shortest path from key $s$ to key $t$ are entered once in sequence. At this time, if key $s$ and key $t$ are the same key, the character will be entered only once.

Given the information about the Tree Keyboard, the keyboard setup operation, and the input operation, create a program to find the number of different character strings that have been input to the computer up to the point immediately after each input operation.

Input

The input is given in the following format.

$N$
$k_1$
$k_2$
:
$k_N$
$u_1$ $v_1$
$u_2$ $v_2$
:
$u_{N-1}$ $v_{N-1}$
$Q$
$q_1$
$q_2$
:
$q_Q$

In the first line, the number of keys $N$ ($1 \leq N \leq 100,000$) is given. In the following $N$ line, the first lowercase letter $k_i$ set for key $i$ is given. In the following $N-1$ line, the wire information is given. The $u_i$ and $v_i$ ($1 \leq u_i < v_i \leq N$) are the numbers of the keys that the $i$th wire connects to.

In the following line, the number of operations $Q$ ($1 \leq Q \leq 100,000$) is given. In the succeeding $Q$ lines, each operation is given in the following form.

1 $s$ $t$

or

2 $k$ $c$

1 $s$ $t$ represents the input operation of hitting key $s$ ($1 \leq s \leq N$) and key $t$ ($1 \leq t \leq N$) in sequence. 2 $k$ $c$ represents the setting operation to change the printed character of key $k$ ($1 \leq k \leq N$) to lowercase English $c$.

Output

After each input operation, output the number of different strings that have been entered into the computer up to that point, each on a single line.

Sample Input and Output

Sample Input

6
a
b
a
c
e
b
1 2
2 3
2 4
2 5
5 6
4
1 1 6
1 3 4
2 5 c
1 1 5

Sample Output

1
2
2

---