Limits 2s, 512 MB

Father works for rail stations and his job is to supply and monitor equipment at the stations. The rail stations are connected with bidirectional railways, and each station can be reached from all other stations without forming any cycles. The equipment is measured by weight.

Father has to supply the equipment to the stations and also monitor the equipment weights frequently. He visits the stations in a manner where he checks all the station equipment from a starting station to a destination station. Sometimes, the equipment becomes unusable or problems occur, and the station master reports these issues. Father then replaces the equipment with new ones (not necessarily of the same weight) quickly.

Nowadays, Father is suffering from sickness, and he wants his two lazy sons, Alice and Bob, to take over his work. Despite their reluctance, Father divides the tasks between them. He assigns Alice to supply the equipment and Bob to monitor the equipment.

Alice and Bob are lazy, and they do not perform their tasks properly. When Father asks Alice to supply equipment to a station, Alice changes the weight of the equipment by its number of divisors.

When Father asks Bob to monitor equipment from station UU to station VV, Bob only monitors those equipment weights that he hasn't monitored earlier during this specific visit from UU to VV. He skips some stations' equipment and only checks stations further along the path from UU to VV.

Father does not care about the equipment weight changed by Alice because it is easy to figure out. However, he wants to know how many stations' equipment Bob skipped each time Father asks Bob to monitor.

There are NN stations numbered from 11 to NN, connected by N1N-1 roads. One can reach every station from every other using the roads. Initially, Father gives Alice an array of weights SS, and Alice is supposed to supply the equipment with weight SiS_i to the ii-th station for 1iN1\leq i\leq N.

There will also be QQ tasks. A task will be for Alice if it starts with A\texttt{A} or it will be for Bob if it starts with B\texttt{B}.

For Alice's task, a station with the number UU and the equipment weight WW will be given. Alice is supposed to supply the equipment with weight WW to the station UU.

For Bob's task, a starting station UU and a destination station VV will be given. Bob has to monitor the equipments along the simple path from UU to VV.

Since Bob always skips the weight he did monitor earlier during that specific visit from UU to VV, Father asks you to find the number of stations whose equipment Bob skipped.

Input

The first line contains two integers NN and QQ, representing the number of stations and the number of tasks, respectively.

The second line contains an array SS of NN integers, where SiS_i indicates the initial equipment weight of the ii-th station, which is supposed to be supplied by Alice initially.

The next N1N-1 lines describe the connections between stations. Each line contains two integers UU and VV, indicating a connection between stations UU and VV.

Finally, there will be QQ lines describing the tasks. Each task is either of the form A U W\texttt{A }U~W or B U V\texttt{B }U~V.

Constraints

  • 1N,Q,U,V2×1051 \leq N, Q, U, V \leq 2 \times 10^5

  • 1Si,W1061 \leq S_i, W \leq 10^6

Output

For each task of type B U V\texttt{B }U~V, you have to print the number of stations that Bob skipped while visiting UU to VV.

Sample

InputOutput
8 7
10 12 16 20 15 26 25 7
1 2
3 1
4 8
1 4
2 5
6 7
2 6
B 5 7
B 6 3
B 7 8
A 4 24
B 7 8
A 2 21
B 5 7
1
1
2
1
2

After the changes of Alice, the initial SS will be [4,6,5,6,4,4,3,2][4, 6, 5, 6, 4, 4, 3, 2].


Submit

Login to submit.

Statistics

69% Solution Ratio
PromodEarliest, 8M ago
sakib_safwanFastest, 0.4s
Eleus_AhammadLightest, 49 MB
Ahamed210Shortest, 3340B
Toph uses cookies. By continuing you agree to our Cookie Policy.