There are N sequences. All of them are initially empty, and you are given a variable lastans = 0. You are given Q queries of two different types:
- “1 x y” – Insert y at the end of the ((x XOR lastans) mod N)th sequence.
- “2 x y” – Print the value of the (y mod size)th element of the ((x XOR lastans) mod N)th sequence. Here, $size$ denotes the size of the related sequence. Then, assign this integer to lastans.
Note: You may assume that, for the second type of query, the related sequence will not be an empty sequence. Sequences and the elements of each sequence are indexed by zero-based numbering.
You can get more information about XOR from Wikipedia. It is defined as ^ in most of the modern programming languages.
The first line consists of $N$, number of sequences, and $Q$, number of queries, separated by a space. The following $Q$ lines contains one of the query types described above.
1 < N,Q < 10^5
0 < x < 10^9
0 < y < 10^9
For each query of type two, print the answer on a new line.
2 5 1 0 5 1 1 7 1 0 3 2 1 0 2 1 1
The first sequence is 5, 3 and the second sequence is 7.