Joos

Time Limit : 1 seconds
Memory Limit : 256 megabytes

Shengdebao had grown tired of the everyday life he had, so he decided to write down a set of letters around a circle. Mehrdad also had a string made up of lower case English letters. Shengdebao then decided to start from one letter on that circle and go around it in clockwise direction.

If at any point of time the string that Shengdebao makes by turning around the circle becomes equal to the one Mehrdad has, Mehrdad is obligated to give Shengdebao a prize! (or *"Shirini"* as they call it!)

Shengdebao wants to know whether he can or cannot receive a prize, and for that reason he has asked you to help him solve this problem.

Input🔗

In the first line of the input string $s$ is given that is actually the string written around the circle. In the second line string $p$ is given which is Mehrdad's string.

$1 \le |s| , |p| \le 1\ 000$

Both strings are made up of lower case English letters.

Output🔗

In the only line of output print "Yes" if Shengdebao can receive the prize and "No" if not.

Examples🔗

Sample input 1🔗

abcab
ababcabab

Sample output 1🔗

Yes

Explanation: by starting from the 4th character the string $p$ can be made.

Sample input 2🔗

abcd
bcdabd

Sample output 2🔗

No

+ Time Limit : 1 second + Memory Limit : 256 megabytes ------------------------ Mr. $A$, $B$, and $C$ have decided to organize a programming contest so *Shengdebao* can take part in it! To make the contest they have to arrange a meeting and talk today but they are quite tired and decided to start a video chat instead. For the video chat to be beneficial they have to talk constantly for exactly 15 minutes and to do this their computer systems should be plugged and have electricity. The thing is $A$, $B$ and $C$ live in different locations of the city and due to the over usage of electricity the power department of the city cuts down the power of various locations in some time intervals. For these three people we know exactly when their power will be cut! You should find out exactly the first time they can start their video chat meeting for 15 minutes. To clarify, you should say the starting time of the 15 minutes interval which all of the three have power and can start the video chat that also ends until 12:00 am! # Input The input contains 3 lines each denoting the intervals in which they don't have any electricity. The first, second and third line indicates the times for $A$, $B$ and $C$ in the same order. In each line a number $k$ is given and afterwards $2k$ strings are given in the format $HH:MM:SS$ each string is a given time with $HH$ being the hour $MM$ being the minute and $SS$ being the second. This means from the time between the first and second , $3$rd and $4$th , $5$th and $6$th , ... , $2k-1$ and $2k$ that particular person does not have power. $$0 \le k \le 10 $$ $$0 \le HH \lt 24$$ $$0 \le MM \lt 60$$ $$0 \le SS \lt 60$$ If there is not any power from second $l$ to second $r$ it means the interval is **inclusive** meaning there is no electricity from the beginning of second $l$ till the end of second $r$ in the interval $[l , r]$. The given $HH$, $MM$ and $SS$ all have 2 digits for example for representing 6 o'clock in the format it should be written as $06:00:00$ # Output Output the first time they can have that meeting in the $HH:MM:SS$ format, meaning they can start talking for 15 minutes in hour $HH$ minute $MM$ and second $SS$. If they cannot talk for 15 at all you should output "$-1$". # Examples ## Sample input 1 ``` 1 00:01:02 03:04:05 1 06:07:08 09:10:11 0 ``` ## Sample output 1 ``` 03:04:06 ``` ## Sample input 2 ``` 1 00:00:00 23:55:00 1 05:06:07 08:00:00 2 01:11:59 22:21:20 22:21:21 22:21:21 ``` ## Sample output 2 ``` -1 ```

!Economize

Time Limit : 1 second
Memory Limit : 256 megabytes

Mr. $A$ , $B$ , and $C$ have decided to organize a programming contest so Shengdebao can take part in it! To make the contest they have to arrange a meeting and talk today but they are quite tired and decided to start a video chat instead.

For the video chat to be beneficial they have to talk constantly for exactly 15 minutes and to do this their computer systems should be plugged and have electricity.

The thing is $A$ , $B$ and $C$ live in different locations of the city and due to the over usage of electricity the power department of the city cuts down the power of various locations in some time intervals.

For these three people we know exactly when their power will be cut! You should find out exactly the first time they can start their video chat meeting for 15 minutes. To clarify, you should say the starting time of the 15 minutes interval which all of the three have power and can start the video chat that also ends until 12:00 am!

Input🔗

The input contains 3 lines each denoting the intervals in which they don't have any electricity. The first, second and third line indicates the times for $A$ , $B$ and $C$ in the same order. In each line a number $k$ is given and afterwards $2k$ strings are given in the format $HH:MM:SS$ each string is a given time with $HH$ being the hour $MM$ being the minute and $SS$ being the second. This means from the time between the first and second , $3$ rd and $4$ th , $5$ th and $6$ th , ... , $2k-1$ and $2k$ that particular person does not have power.

$0 \le k \le 10$ $0 \le HH \lt 24$ $0 \le MM \lt 60$ $0 \le SS \lt 60$

If there is not any power from second $l$ to second $r$ it means the interval is inclusive meaning there is no electricity from the beginning of second $l$ till the end of second $r$ in the interval $[l , r]$ .

The given $HH$ , $MM$ and $SS$ all have 2 digits for example for representing 6 o'clock in the format it should be written as $06:00:00$

Output🔗

Output the first time they can have that meeting in the $HH:MM:SS$ format, meaning they can start talking for 15 minutes in hour $HH$ minute $MM$ and second $SS$ . If they cannot talk for 15 at all you should output " $-1$ ".

Examples🔗

Sample input 1🔗

1 00:01:02 03:04:05
1 06:07:08 09:10:11
0

Sample output 1🔗

03:04:06

Sample input 2🔗

1 00:00:00 23:55:00
1 05:06:07 08:00:00
2 01:11:59 22:21:20 22:21:21 22:21:21

Sample output 2🔗

-1

+ Time Limit : 1 seconds + Memory Limit : 256 megabytes --------------------------- *Shengdebao* has recently created a bank account, and being a cautious fellow, he wants to make sure of the bank's security policies. Financial experts have come up with a new formula to calculate the amount of security in a bank account. They introduce the amount of security as a quantity represented by a number, this number is calculated as follows: If a bank has $n$ doors and $k$ seats this value is equal to the number of ways to choose $k$ distinct numbers from $1$ to $n$ so that if we write the pairwise difference between any two (the difference between numbers $a$ and $b$ is expressed as $|a-b|$) values (which will be exactly $\frac{k \times (k-1)}{2}$ values), the *gcd* (greatest common divisor) of **every pair** of these $\frac{k \times (k-1)}{2}$ integers will be $1$ or in other words these values must be pairwise coprime! *Shengdebao* was quite surprised by the formula and could not find the relevency between this and the security, but who is he to question the experts! So he started counting the number of doors and seats in his bank. Given the number of doors and seats, help him calculate the amount of security in his bank account. # Input In the only line of input the values $n$ (number of doors) and $k$ (the number of seats) are given in the same order. $$ 1 \le n , k \le 2\ 000$$ # Output Output only one line the security of the bank. Since the number can be quite large output it modulo $10^9 + 7$. # Examples ## Sample input 1 ``` 4 4 ``` ## Sample output 1 ``` 0 ``` ## Sample input 2 ``` 4 3 ``` ## Sample output 2 ``` 4 ``` *Explanation:* In this test if we choose three distinct numbers in **anyway** the conditions will be satisfied. For example by choosing 1 , 2 and 4 the differences will be equal to 1 , 2 and 3 which are pairwise coprime. ## Sample input 3 ``` 5 2 ``` ## Sample output 3 ``` 10 ``` *Explanation:* Any pair of numbers chosen will only make exactly **one** difference which satisfies the criteria.

Gheyme

Time Limit : 1 seconds
Memory Limit : 256 megabytes

Shengdebao has recently created a bank account, and being a cautious fellow, he wants to make sure of the bank's security policies.

Financial experts have come up with a new formula to calculate the amount of security in a bank account. They introduce the amount of security as a quantity represented by a number, this number is calculated as follows:

If a bank has $n$ doors and $k$ seats this value is equal to the number of ways to choose $k$ distinct numbers from $1$ to $n$ so that if we write the pairwise difference between any two (the difference between numbers $a$ and $b$ is expressed as $|a-b|$ ) values (which will be exactly $\frac{k \times (k-1)}{2}$ values), the gcd (greatest common divisor) of every pair of these $\frac{k \times (k-1)}{2}$ integers will be $1$ or in other words these values must be pairwise coprime!

Shengdebao was quite surprised by the formula and could not find the relevency between this and the security, but who is he to question the experts! So he started counting the number of doors and seats in his bank.

Given the number of doors and seats, help him calculate the amount of security in his bank account.

Input🔗

In the only line of input the values $n$ (number of doors) and $k$ (the number of seats) are given in the same order.

$1 \le n , k \le 2\ 000$

Output🔗

Output only one line the security of the bank. Since the number can be quite large output it modulo $10^9 + 7$ .

Examples🔗

Sample input 1🔗

4 4

Sample output 1🔗

Sample input 2🔗

4 3

Sample output 2🔗

Explanation: In this test if we choose three distinct numbers in anyway the conditions will be satisfied.

For example by choosing 1 , 2 and 4 the differences will be equal to 1 , 2 and 3 which are pairwise coprime.

Sample input 3🔗

5 2

Sample output 3🔗

Explanation: Any pair of numbers chosen will only make exactly one difference which satisfies the criteria.

+ Time Limit : 1 second + Memory Limit : 256 megabytes ------------------------------ It is the well-known annual day *"Tavalbao"* , *Shengdebao*'s birthday! In his birthday he has received gifts from all his friends and relatives. One particular present appeared the most interesting, A digraph (Directed Graph) which has $n$ vertices and $m$ directed edges. On vertex $i$ number $a_i$ is written. After his birthday party *Shengdebao* got bored and started traversing the graph. He decided to start from an arbitrary vertex $v$ and start traversing some edges in their directions. While doing so, he wanted to keep track of a number $x$. Initially number $x$ is equal to $a_v$ (the label written on the starting vertex) after passing an edge $a \to b$ he will write $a_b$ after the last digit of $x$. For example if he starts from vertex $2$ with label $123$ and goes to vertex $1$ with label $78$ we will have $x = 12378$. He intends to traverse over a walk (this walk can contain repeated edges or vertices) and write down number $x$ so that $x$ has exactly $k$ digits, since $k$ is his favorite number, and between all the available ways, $x$ should be **maximized**. You're *Shengdebao*'s friend so give the guy a hand and help him! # Input In the first line numbers $n , m , k$ are given denoting the number of vertices , edges and *Shengdebao*'s favorite number in order. Next line contains $n$ integers one after another, $i$th integer is equal to $a_i$. (the number written on vertex $i$) Afterwards $m$ lines each consisting of two integers $u , v$ are given showing edge $u \to v$ exists in the graph. $$ 1 \le u,v \le n $$ $$ n,m,k \le 1\ 000 $$ $$1 \le a_i \le 100\ 000 $$ The graph can contain loops or multiple edges. # Output In the only line of output display the $k$ digit number $x$ that is maximized. Display $-1$ if no answer exists! # Examples ## Sample input 1 ``` 5 4 3 4 12 3 1 1 1 2 2 3 1 4 4 5 ``` ## Sample output 1 ``` 412 ``` ## Sample input 2 ``` 3 3 8 1 2 3 1 2 2 3 3 1 ``` ## Sample output 2 ``` 31231231 ``` ## Sample input 3 ``` 3 3 8 12 251 3200 1 2 2 3 3 1 ``` ## Sample output 3 ``` -1 ```

Tavalbao

Time Limit : 1 second
Memory Limit : 256 megabytes

It is the well-known annual day *"Tavalbao"* , Shengdebao's birthday!

In his birthday he has received gifts from all his friends and relatives. One particular present appeared the most interesting, A digraph (Directed Graph) which has $n$ vertices and $m$ directed edges. On vertex $i$ number $a_i$ is written. After his birthday party Shengdebao got bored and started traversing the graph. He decided to start from an arbitrary vertex $v$ and start traversing some edges in their directions. While doing so, he wanted to keep track of a number $x$ . Initially number $x$ is equal to $a_v$ (the label written on the starting vertex) after passing an edge $a \to b$ he will write $a_b$ after the last digit of $x$ .

For example if he starts from vertex $2$ with label $123$ and goes to vertex $1$ with label $78$ we will have $x = 12378$ .

He intends to traverse over a walk (this walk can contain repeated edges or vertices) and write down number $x$ so that $x$ has exactly $k$ digits, since $k$ is his favorite number, and between all the available ways, $x$ should be maximized.

You're Shengdebao's friend so give the guy a hand and help him!

Input🔗

In the first line numbers $n , m , k$ are given denoting the number of vertices , edges and Shengdebao's favorite number in order.

Next line contains $n$ integers one after another, $i$ th integer is equal to $a_i$ . (the number written on vertex $i$ )

Afterwards $m$ lines each consisting of two integers $u , v$ are given showing edge $u \to v$ exists in the graph.

$1 \le u,v \le n$ $n,m,k \le 1\ 000$ $1 \le a_i \le 100\ 000$

The graph can contain loops or multiple edges.

Output🔗

In the only line of output display the $k$ digit number $x$ that is maximized.

Display $-1$ if no answer exists!

Examples🔗

Sample input 1🔗

Sample output 1🔗

Sample input 2🔗

Sample output 2🔗

31231231

Sample input 3🔗

3 3 8
12 251 3200
1 2
2 3
3 1

Sample output 3🔗

-1

+ Time Limit : 2 second + Memory Limit : 256 megabytes --------------------- *Shengdebao* is quite a dreamer, thereby dreams a lot! In a dream he had last night people built a whole city named *"Shengdepolis"* in his favour! For the opening of this magnificent city people invited him on a tour expressing the city's impressive features. *Shengdebao* started describing it for you: I entered the city and the first thing I noticed was $n$ towers, some of them were glowing with a beautiful purple light. There were some elevated railroads between some pairs of towers, each railroad was between two **distinct** towers. Some of the railroads were *magical* meaning they could disappear! The highlighted thing was the city's diverse architecture. The lighting of the towers were related to the visible railways. By paying close attention I found out that at any point of time a tower glows purple only when there are **Odd number of visible railroads** connected to them. Some of the railways aren't magical and so are always visible, these railroads are always counted in their adjacent towers. Their tour program was also interesting! The tour contained a set of **turns**, in each *turn* I start by observing the city from a purple luminous tower. A helicopter then comes and takes me to **another glowing** tower. In **both before and after the trip with the helicopter** I take a glance at the landscape. Then after I've took a glance at the landscape on the second tower, the magic happens! some of the magical railroads appear and some disappear, leading to a change in the city's lighting (it is possible that the city doesn't change at all), but the change **must** be in a way that the tower I'm on top of **stays luminous** (meaning **odd** number of **visible** railways should stay connected to it). After the change, the *turn* ends starting a new turn afterwards or ending the tour. These turns start from one Tower and **should end at the same tower**. I remember agreeing to this tour in two conditions: + For **all possible ways of architectures** (meaning the ways which magical railways are visible or not) and **every glowing tower in that form** I should have a view of the city from the top of that tower. meaning if we have $x$ magical railways, for all $2^x$ possible city formats and each glowing tower in every format I should have **at least one** glance of that landscape in either before or after my trip with the helicopter in a *turn*. + The number of *"turns"* should be minimized. The story ends! *Shengdebao* has an identical memory and remembers each detail about the magical city. But he didn't keep track of the number of *turns* in his tour so you should help him find out a valid tour with minimum size. Also if the number of *turns* in the dreamy tour is more than $1\ 000\ 000$ the fact that *Shengdebao* is lying about his dream is in prospect! so if there is no tour with less than $1\ 000\ 000$ *turns*, you should say he is lying! # Input In the input *Shengdepolis* is given. First line contains $n , m$ the number of towers and railways respectively. Then in the next $m$ lines the explanation of each railroad is given by three integers $t , u , v$. $t$ is either $0$ or $1$ if it is $0$ it means that the railway between towers number $v$ and $u$ is **not magical** and if $t = 1$ then it is **magical**. $$1 \le n , m \le 17$$ $$0 \le t \le 1 , 1 \le u , v \le n , u \neq v$$ It is possible for two railways to be **exactly the same**. # Output In the first line of output you should write the minimum number of *turns* in the imaginary tour represented as a number $k$. Then if $k$ is greater than $1\ 000\ 000$ you should display *"lie"* and end the program. If the condition $k \le 1\ 000\ 000$ holds you should output $k$ lines each consisting of 3 integers $u , mask , v$. $u$ represents the tower on which *Shengdebao* starts that *turn* and $v$ shows the one which he ends at after riding the helicopter. $mask$ is a code showing the architecture of the city. A code of a city format is described below: $mask$ is a number less than $2 ^ m$ that when written in the binary notation the $i$th bit is either equal to $0$ or $1$ if it is equal to $0$ it means that the $i$th edge is **invisible** in this form and otherwise this bit is $1$. The number of each edge is **in the order appeared in the input**. By this explanation there **does not exist** any $mask$ in which its $i$th bit is $0$ with also the first integer in the $i+1$th line of input being $0$ at the same time. To clarify, in each line $u$ and $v$ both have **Odd** number of visible railways connected to them in the format coded as $mask$. The $i$th line's third number should be equal to the $i+1$th line's first number and the first number of the first line should be equal to the last number of the $k$th line. If there are multiple tours satifsying the criteria, you can output an arbitrary one. # Examples ## Sample input 1 ``` 3 2 0 1 2 0 2 3 ``` ## Sample output 1 ``` 2 1 3 3 3 3 1 ``` *Explanation:* No railroad is magical so always towers $1$ and $3$ have $1$ visible adjacent railroads and they are always visible and the code is always $3$ (both railways are visible). By considering that the tour should contain the only architecture from both scenes from tower $1$ and $3$, and also the fact that we should return to the same tower, its best to go from $1$ to $3$ and return back to $1$ again. ## Sample input 2 ``` 4 6 0 1 2 0 2 3 0 3 4 0 4 1 1 1 3 1 2 4 ``` ## Sample output 2 ``` 4 1 63 4 4 47 2 2 63 3 3 31 1 ``` ## Sample input 3 ``` 3 2 0 1 2 1 2 3 ``` ## Sample output 3 ``` 4 1 3 3 3 3 1 1 1 2 2 1 1 ```

Diversity

Time Limit : 2 second
Memory Limit : 256 megabytes

Shengdebao is quite a dreamer, thereby dreams a lot! In a dream he had last night people built a whole city named *"Shengdepolis"* in his favour! For the opening of this magnificent city people invited him on a tour expressing the city's impressive features. Shengdebao started describing it for you:

I entered the city and the first thing I noticed was $n$ towers, some of them were glowing with a beautiful purple light. There were some elevated railroads between some pairs of towers, each railroad was between two distinct towers. Some of the railroads were magical meaning they could disappear! The highlighted thing was the city's diverse architecture. The lighting of the towers were related to the visible railways. By paying close attention I found out that at any point of time a tower glows purple only when there are Odd number of visible railroads connected to them. Some of the railways aren't magical and so are always visible, these railroads are always counted in their adjacent towers.

Their tour program was also interesting! The tour contained a set of turns, in each turn I start by observing the city from a purple luminous tower. A helicopter then comes and takes me to another glowing tower. In both before and after the trip with the helicopter I take a glance at the landscape. Then after I've took a glance at the landscape on the second tower, the magic happens! some of the magical railroads appear and some disappear, leading to a change in the city's lighting (it is possible that the city doesn't change at all), but the change must be in a way that the tower I'm on top of stays luminous (meaning odd number of visible railways should stay connected to it). After the change, the turn ends starting a new turn afterwards or ending the tour. These turns start from one Tower and should end at the same tower.

I remember agreeing to this tour in two conditions:

For all possible ways of architectures (meaning the ways which magical railways are visible or not) and every glowing tower in that form I should have a view of the city from the top of that tower. meaning if we have $x$ magical railways, for all $2^x$ possible city formats and each glowing tower in every format I should have at least one glance of that landscape in either before or after my trip with the helicopter in a turn.
The number of *"turns"* should be minimized.

The story ends!

Shengdebao has an identical memory and remembers each detail about the magical city. But he didn't keep track of the number of turns in his tour so you should help him find out a valid tour with minimum size. Also if the number of turns in the dreamy tour is more than $1\ 000\ 000$ the fact that Shengdebao is lying about his dream is in prospect! so if there is no tour with less than $1\ 000\ 000$ turns, you should say he is lying!

Input🔗

In the input Shengdepolis is given. First line contains $n , m$ the number of towers and railways respectively. Then in the next $m$ lines the explanation of each railroad is given by three integers $t , u , v$ . $t$ is either $0$ or $1$ if it is $0$ it means that the railway between towers number $v$ and $u$ is not magical and if $t = 1$ then it is magical.

$1 \le n , m \le 17$

$0 \le t \le 1 , 1 \le u , v \le n , u \neq v$

It is possible for two railways to be exactly the same.

Output🔗

In the first line of output you should write the minimum number of turns in the imaginary tour represented as a number $k$ . Then if $k$ is greater than $1\ 000\ 000$ you should display *"lie"* and end the program. If the condition $k \le 1\ 000\ 000$ holds you should output $k$ lines each consisting of 3 integers $u , mask , v$ . $u$ represents the tower on which Shengdebao starts that turn and $v$ shows the one which he ends at after riding the helicopter. $mask$ is a code showing the architecture of the city. A code of a city format is described below:

$mask$ is a number less than $2 ^ m$ that when written in the binary notation the $i$ th bit is either equal to $0$ or $1$ if it is equal to $0$ it means that the $i$ th edge is invisible in this form and otherwise this bit is $1$ . The number of each edge is in the order appeared in the input. By this explanation there does not exist any $mask$ in which its $i$ th bit is $0$ with also the first integer in the $i+1$ th line of input being $0$ at the same time.

To clarify, in each line $u$ and $v$ both have Odd number of visible railways connected to them in the format coded as $mask$ . The $i$ th line's third number should be equal to the $i+1$ th line's first number and the first number of the first line should be equal to the last number of the $k$ th line.

If there are multiple tours satifsying the criteria, you can output an arbitrary one.

Examples🔗

Sample input 1🔗

3 2
0 1 2
0 2 3

Sample output 1🔗

2
1 3 3
3 3 1

Explanation: No railroad is magical so always towers $1$ and $3$ have $1$ visible adjacent railroads and they are always visible and the code is always $3$ (both railways are visible). By considering that the tour should contain the only architecture from both scenes from tower $1$ and $3$ , and also the fact that we should return to the same tower, its best to go from $1$ to $3$ and return back to $1$ again.

Sample input 2🔗

Sample output 2🔗

Sample input 3🔗

3 2
0 1 2
1 2 3

Sample output 3🔗

+ Time Limit : 4 seconds + Memory Limit : 512 megabytes ------------------------- 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. # Input 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$$ # Output For any type two query in one line output the hole as a pair $i \ j$ showing the result of the related patrol. # Examples ## Sample input 1 ``` 4 1 1000000000 1 1000000000 4 2 0 1 3 2 0 1 14 1 1 1 2 0 1 999999999997 ``` ## Sample output 1 ``` 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)$. ## Sample input 2 ``` 3 10 9 10 6 1 0 6 1 1 4 1 1 11 1 2 8 1 2 12 2 0 10 4 ``` ## Sample output 2 ``` 1 4 ``` Explanation : The ant in this patrol goes to heights $9 \to 8 \to 6 \to 4$ respectively

Nano-ant

Time Limit : 4 seconds
Memory Limit : 512 megabytes

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.

Input🔗

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$

Output🔗

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

Examples🔗

Sample input 1🔗

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

Sample output 1🔗

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)$ .

Sample input 2🔗

Sample output 2🔗

1 4

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