Snail List
InterviewTime limit1sMemory limit256 MB
A linked list has a tail node N pointing back to node V, forming one cycle. For each query K, report the value stored in the node reached after moving K steps from node 1.
- Level
Medium5 of 10
- Topics
- Linked list, Array, Math, Implementation
- Solved
- No attempts yet
Problem
Youngjin likes snails. Because he likes them so much, he gave the name snail list to a singly linked list of a particular shape.
Number the nodes of an ordinary linear singly linked list 1, 2, ..., N in the order they are linked. Node N points to nothing, and a list in which node N points to some node other than node 1, forming a cycle, is called a snail list. Each node in a snail list stores one integer.
In other words, a snail list is a linked list shaped as follows. The number inside a node is the value it stores.
"Snail, snail, if I move one step at a time starting from node 1 for a total of K steps, what value is in the node I reach?"
Youngjin sketched a snail list in a dark room, then kept muttering the same sentence over and over, changing only K.
Youngjin does not look well... Let us answer all of his questions before the situation gets worse.
Input
The first line gives the number of nodes N (2 ≤ N ≤ 200,000), the number of queries M (1 ≤ M ≤ 200,000), and the number of the node that node N points to, V (2 ≤ V ≤ N), separated by spaces.
The second line gives N integers C1, C2, …, CN separated by spaces. Here Ci is the value stored in node i. (1 ≤ Ci ≤ 1,000,000)
From the third line, M lines follow, each giving the K for one query (1 ≤ K ≤ 109).
Output
Output the answer to each query over M lines.
Hint
Of course, the last node can also have a cycle that points to itself.
Youngjin calls such a snail list a slug list!