There is a contest with participants.

During the contest, all participants will stand in a line. Every participant has a level 。

In the -th turn, number all participants in the order. Then participants numbered between will have a competition and the one with the maximum level will win. If two or more participants have the same maximum level, then only one of them may win. Then all losers will get out of the line, while others stand in the same order.

Now participants have stood in a line. events follow:

1. A new turn for   has been added to the schedule.

2. Query: if the last participant has a level of and he/she can choose the position to stand at, how many turns he/she can definitely win.


Note that:

1. If the last participant is not in , then he/she is never considered to win in this turn.

2. If in a turn there are two or more participants with the same maximum level, the last participant may lose (not definitely win).

The first line contains two integers  (  ).

The second line contains  integers  (  ), describing the level of the  participants.

Then  line, each line beginning with an integer  (  ).

If , then two integers ,describing a new turn (  ).

If , then an integers , describing a query (  ).

It is guaranteed that in each turn there is at least  participants left.

For every query, output one line containing the position where the number of turns the last participant can definitely win is maximized. If two or more positions satisfy the condition, output the minimum one.

5 8
2 1 3 5
1 2 4
1 1 2
1 1 2
2 4
2 1
2 2
2 3
2 5

2
1
1
1
2