Regional Olympiad Standings

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

The Olympiad is in full swing — the competition favorite, Zenyk, has managed to solve a few problems, but the fierce competition is still ahead.

Participants of the Olympiad on Algotester see only their own result, but do not know how many points others have scored. However, the organizers can observe the full picture — they can see the standings.

There are \(n\) people participating in the Olympiad, numbered from 1 to \(n\). Zenyk competes under the number 1.

The order of participants in the standings is given by a permutation \(p\) of numbers from 1 to \(n\). In the first place in the table is participant number \(p_1\), in the second place — participant \(p_2\), and so on.

During the Olympiad, \(q\) events took place. Events are of three types:

• Given \(t_i\) = 1, \(k_i\). Zenyk solves a problem and overtakes \(k_i\) participants above him in the standings.

• Given \(t_i\) = 2, \(x_i\). The participant with number \(x_i\) overtakes one participant directly above them.

• Given \(t_i\) = 3, \(x_i\) and \(k_i\). The organizers of the Olympiad, with their eyes glued to the table, are interested in the sum of the numbers of the \(k_i\) participants located directly above the participant with number \(x_i\).

The organizers are drinking tea and do not want to calculate anything by themselves. Help them answer their questions.

Input

The first line contains a single integer \(n\) — the number of participants.

The next line contains \(n\) integers \(p_i\), which define the initial order of participants in the standings.

The next line contains a single integer \(q\) — the number of events during the Olympiad.

The following \(q\) lines describe the events.

If the event is of the first type, two integers \(t_i = 1\) and \(k_i\) are given — the event type and the number of participants Zenyk overtakes. There is at least \(k_i\) participants ahead of Zenyk.

If the event is of the second type, two integers \(t_i = 2\) and \(x_i\) are given — the event type and the number of the participant who overtakes the participant above them. Participant \(x_i\) is not the first one.

If the event is of the third type, three integers \(t_i = 3\), \(x_i\), and \(k_i\) are given — the event type, the participant’s number, and the number of participants above them that the organizers are interested in. There are at least \(k_i\) participants ahead of the participant with number \(x_i\).

Output

For each query of the third type — output the sum of the numbers of the \(k_i\) participants above the participant with number \(x_i\).

Constraints

\(2 \le n, q \le 10^6\),

\(1 \le p_i \le n\), all \(p_i\) are distinct,

\(1 \le k_i \le n - 1\), \(1 \le x_i \le n\),

there is at least one query of the third type among the events.

Problem evaluation consists of the following subtasks:

1 point — example from the statement,

4 points — there are only queries of the third type,

10 points — there are only queries of the second and third types,

10 points — without additional constraints.

You will receive points for a subtask only if you give the correct answer to all tests in that subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
3 2 3 1 10 3 3 1 2 3 3 2 1 3 1 2 1 2 3 2 2 2 3 2 2 3 1 1 3 2 1	2 3 5 4 2 3