محدودیت زمان: ۴ ثانیه
محدودیت حافظه: ۵۱۲ مگابایت

Science grows faster nowadays more than ever and scientific achievements increase more and more! One of the greatest achievements in the field of nano technology is being made by a company founded by Shengdebao's brother. The company's name is "BAOCompany" and their new project revolves around tiny ants called nano-ants. Here's some details about them:

Nono-ants should be kept in a form of prism with a regular $n$-sided polygon base with the height of $1$ meters it means if we look at the prism from above we will see a regular $n$ sided polygon and if we put it on the ground it will be $1$ meters high. The $n$ vertical edges of the prism are numbered from $0$ to $n-1$ in clockwise order. There exists a special nano-needle that can put delicate holes on the edges of the prism with nano-meter accuracy. After creating each hole exactly one nano-ant can occupy that hole. In fact each hole can be represented by two integer numbers $(i , j)$ such that $0 \le i \lt n$ and $1 \le j \le 10^9$ meaning the hole is on the $i$th edge and in height $j$ nano-meters.

Baoium, the material used to make the prism, is quite fragile and can't have more than $n \times n$ holes on it. Also at the beginning the prism has exactly one hole placed on each edge.

Nano-ant movements are impressive! Their movements are in the form of $k$-patrols each $k$-patrols takes $k$ days. At the morning of everyday the ant starts from one hole on an edge, the ants takes a peek from the hole to the next edge in clockwise order and chooses the closest to it. If multiple closest holes exists, he chooses one with the lowest height. Then he starts traversing the intended side through a straight line. Nano-ants are tiny so it takes them one day to pass that side and when they reach the next hole in the next edge they become tired and rest in that hole for the night starting tomorrow morning from that hole again. Now in a $k$-patrol this continues for $k$ days, a $k$-patrol's result is the hole in which the ant rests in the last night.

Scientist are testing some of nano-ants properties, their research contains $q$ stages in each stage they either create a new hole on the prism, or they want to know the result of a specific $k$-patrol. $k$ can be a large number so they asked you, their programmer, to help them with this problem.

ورودی

In the first line of input comes number $n$, the number of sides on the prism. Then in the next line $n$ numbers are given in the row number $i$ is equal to $a_i$ indicating the initial hole $(i-1 , a_i)$ on the $i$th edge.

In the third line you should receive number $q$, the number of researches that should be done. next $q$ lines are in two formats:

$1 \ i \ j$ meaning a new hole should be created on height $j$ of the $i$th edge. $(0 \le i \lt n , 1 \le j \le 10^9)$
$2 \ i \ j \ k$ you should output the result of a $k$-patrol commencing from hole $(i,j)$ as a pair of integers $(0 \le i \lt n , 1 \le j \le 10^9 , 0 \le k \le 10 ^ {12})$

It is guaranteed that the first type researches do not repeat and every time a new hole is created. Also, the next type of research always refers to a preceding created hole and not a hole not yet made.

$$ 3 \le n \le 300 $$ $$ 0 \le q \le n \times n - n$$

خروجی

For any type two query in one line output the hole as a pair $i \ j$ showing the result of the related patrol.

مثال

ورودی نمونه ۱

4
1 1000000000 1 1000000000
4
2 0 1 3
2 0 1 14
1 1 1
2 0 1 999999999997

خروجی نمونه ۱

3 1000000000
2 1
1 1

Explanation: Before the addition of the new hole each hole has a unique destination on the next edge and the answer is uniquely determined from $k \ mod \ n$. After adding the new hole in the last patrol, by passing over $999\ 999\ 999\ 996$ sides the ant then returns to its former place $(1 , 0)$ and in the next stage it goes to the next closest hole (the new hole) $(1 , 1)$.

ورودی نمونه ۲

خروجی نمونه ۲

1 4

Explanation : The ant in this patrol goes to heights $9 \to 8 \to 6 \to 4$ respectively

ارسال پاسخ برای این سؤال