Easy Queries

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given an array A consisting of N positive integers. You have to answer Q queries on it of following type:
 l r k : Let S denote the sorted (in increasing order) set of elements of array A with its indices between l and r. Note that set S contains distinct elements (i.e. no duplicates).
You need to find k^{th} number in it. If such a number does not exist, i.e. the S has less than k elements, output 1.
All the indices in the queries are 1based.
Input
The first line of input contains two space separated integers N and Q denoting the number of elements in A, and the number of queries, respectively.
The second line of input contains N space separated integers denoting the array A.
Each of the next Q lines contains five integers a_{i}, b_{i}, c_{i}, d_{i}, k_{i}.
We will generate l_{i}, r_{i} indices for this query as follows:
Let answer for i  1^{th} query equal ans_{i  1}. For 0^{th} query ans_{0} = 0. Define l_{i} = (a_{i} x max(ans_{i  1}, 0) + b_{i}) mod N + 1, r_{i} = (c_{i} x max(ans_{i1}, 0) + d_{i}) mod N + 1. If l_{i} > r_{i}, then swap l_{i} and r_{i}.
Output
For each query, output the answer to the query in a single line. If such a number doesn't exist, output 1.
Constraints
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ A_{i} ≤ 10^{9}
 0 ≤ a_{i}, b_{i}, c_{i}, d_{i} ≤ N
 1 ≤ l_{i} ≤ r_{i} ≤ N
 1 ≤ k_{i} ≤ N
Example
Input: 4 4 3 2 1 2 0 1 0 3 2 2 0 0 3 4 1 2 1 3 2 2 0 0 3 3 Output: 2 1 2 3 Input: 10 10 9 10 6 3 8 4 9 6 4 10 0 2 0 9 3 1 9 1 3 3 1 8 1 0 3 1 2 1 7 2 1 6 1 2 3 1 4 1 3 1 1 6 1 6 1 1 4 1 8 1 1 9 1 3 3 1 9 1 2 1 Output: 6 9 10 4 6 3 10 4 6 4
Subtasks
 Subtask #1 (10 points) : Q x N ≤ 10^{7}
 Subtask #2 (20 points) : k_{i} = 1
 Subtask #3 (30 points) : a_{i} = 0, c_{i} = 0
 Subtask #4 (40 points) : Original constraints
Explanation
Example #1:
Query 1. Sorted set of elements : {1, 2}. Second number in this is 2.
Query 2. Sorted set of elements : {1, 2, 3}. Fourth number doesn't exist, hence answer is 1.
Query 3. Sorted set of elements : {1, 2}. Second number in this set is 2.
Query 4. Sorted set of elements : {1, 2, 3}. Third number in this set is 3.
Author:  mgch 
Tester:  kevinsogo 
Editorial  http://discuss.codechef.com/problems/DISTNUM2 
Tags  funtionalds, hard, may16, mgch, rangetree, segmenttree 
Date Added:  23082015 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 