Doraemon has an array A of N positive integers. He asks Q queries on this array. Each queries are of type : L, R, X, K. For $i^{th}$ query P and Q are generated from L, R and answer for $(i-1)^{th}$ query (suppose previous_query_answer) as following pseudocode:

P = (L + previous_query_answer) % N + 1
Q = (R + previous_query_answer) % N + 1
if ( $P > Q$ ) swap(P, Q)

For 1st query previous_query_answer = 0.
Answer to the query is count of all elements Y in subarray $A[P....Q]$ such that $|X - Y| <= K$. Show him that you are a pro by answering the queries.

Input Format :

First line of input contains integer N - size of array. Next line contains N integers of array. Next line contains integer Q - number of queries. Next Q line contains queries of type : L R X K as mentioned in problem statement.

Output Format :

For each query print the required answer per line.

Constraints :

1 <= N <= $10^5$
1 <= Q <= $10^5$
1 <= $A_i$ <= $10^9$
1 <= L <= R <= $10^5$
0 <= $X, K$ <= $10^9$

Setter : Tanmay Patel

Tester: Mohib Manva