HackerRank: DynamicArray

Problem Statement

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.

Input Format

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.

Constraints
1 < N,Q < 10^5
0 < x < 10^9
0 < y < 10^9

Output Format

For each query of type two, print the answer on a new line.

Sample Input

2 5
1 0 5
1 1 7
1 0 3
2 1 0
2 1 1

Sample Output

7
3

Explanation

The first sequence is 5, 3 and the second sequence is 7.

Solution:

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.