Description

We all know that elephants have incredible memory, as each one has a name and a lucky number.

elfnt can remember up to $n$ friends, storing them in his memory list.
There are $q$ queries, each belonging to one of the following types:

• ASK name: Check if elfnt remembers an elephant with the given name.

  • If found in memory, print its lucky number and refresh the impression of it by moving it to the front of the list.
  • Otherwise, print "Who?".

• ADD name num: Introduce a new elephant with name and lucky number num.

  • Otherwise, add it to the front of the list.
  • If memory is full, remove the least recently used (ask or add) elephant before adding the new one.

It is guaranteed that NO same name will be added more than once using the ADD operation.

Input

The first line contains two integers $n$ and $q$, representing the size of the memory list and the query times.

The following $q$ lines, each contains a type of operation. The format are as follow.

• ADD name num
• ASK name

Constraints

• $1 \leq n \leq 5000$
• $1 \leq q \leq 2 \times 10^5$
• $1 \leq |$ name $| \leq 100$
• $1 \leq $ num $\leq 10^9$
• The name only contains lowercase letters.

Subtask

1. (Testcases 1-3) $1 \leq n, q \leq 1000$
2. (Testcases 4-8) At most $2000$ ASK queries.
3. (Testcases 9-10) No additional constraints.

Output

For each ASK query:

• Print the lucky number if name is found in memory.
• Otherwise, print "Who?".

Each output should be followed by a newline.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an array of size $N$, find the inversion count in the array. Two array elements $arr[i]$ and $arr[j]$ form an inversion if $arr[i] > arr[j]$ and $i < j$.

Input

The first line contains an integer $N$, represents the size of the array.

The following one line contains $N$ integers, represent the elements in the array.

Contraints

• $1 \le N, arr[i] \le 5*10^5$

Subtask

1. (Testcases 1-5) $1 \le N \le 10^3$
2. (Testcases 6-10) No additional constraints.

Output

Output the number of inversions. You should not output a new line ('\n') after your answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Thanksone likes to eat apple too much so he planted an ordinary apple tree.

We can view the ordinary apple tree as a tree with $N$ nodes and the root is $R$. Initially, there would be some apples on each of the nodes.

Then, during the following $M$ days, one of the two things might happen on the $i$-th day:

1. $k_i$ apples would grow on node $x_i$.
2. A pigeon would eat $k_i$ apples from "node $x_i$ and all the neighboring nodes of $x_i$".

Finally, there will be $Q$ queries, for $i$-th query, please help Thanksone to track how many apples are there in the subtree of $x_i$.

Input

The first line contains four integers $N$, $M$, $R$ and $Q$, representing $N$ nodes, $M$ days, the root $R$ and $Q$ queries.

Following are $N-1$ lines, each contains two integers $u_i$, $v_i$, representing a directed edge pointing from $u_i$ to $v_i$.

The following one line contains $N$ integers, representing the initial amount of apples on each nodes.

Next, the following $M$ lines, each contains three integers $o_i$, $k_i$, $x_i$.

1. If $o_i = 1$, it means that $k_i$ apples grew on node $x_i$ on the $i$-th day.
2. If $o_i = 2$, it means that a pigeon ate $k_i$ apples from "node $x_i$ and all the neighboring nodes of $x_i$" on the $i$-th day.

Finally, the following $Q$ lines, each contains an integers $x_i$, representing the node which we want to know 

Constraints

• $1 \le N, M, Q \le 2*10^5$
• $1 \le R \le N$
• $o_i = {1, 2}$
• $1 \le k_i \le 1*10^9$
• $1 \le x_i \le N$

It is guaranteed that the number of operation 2 ($o_i = 2$) won't exceed 200.
It is guaranteed that the number of apples would be nonnegative.

Subtask

1. (Testcases 1-3) $1 \le N, M, Q \le 10^3$
2. (Testcases 4-6) $o_i = 1$
3. (Testcases 7-10) No additional constraints.

Output

Output $Q$ lines, for $i$-th line, output the number of apples there are in the subtree of $x_i$.

Sample Input  Download

Sample Output  Download

Tags

Discuss