|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|7 초||32 MB||4||1||1||25.000%|
Professor G. Reedy is writing a computer program, which will help him to earn a lot of money from buying and selling shares on a stock exchange. He is particularly interested in shares of company called Noway. Professor knows that the key to success is careful examination of a stock exchange’s history. He was observing share prices for n days and he knows that on i-th day Noway’s share was worth pi dollars (1 ≤ i ≤ n). For simplicity you can assume that all prices are different.
Professor would like to do m queries on this data and he need your help in writing module which will answer these queries. He is mainly interested in queries of form <b,e,l,u> which encodes following question: for how many days from b-th to e-th day (inclusive) the price of Noway’s share was between l and u dollars (inclusive)?
Professor will test your module in a strange way. For an i-th query (1 ≤ i ≤ m) he will give you four integers: bi, ei, li and ui. You will have to calculate integersi — an answer to a query <bi,ei,li+si−1,ui+si−1> (where si−1 is an answer to the previous query). Assume that s0 = 0.
Write a program which:
The first line of input contains two integers n and m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 1000000), separated with a space. The next n lines describe price fluctuations of shares: line number i+1 contains integer pi (1 ≤ pi ≤ 109). The next m lines describe professor’s queries: line number i+n+1 contains four integers bi, ei, li and ui (1 ≤ bi ≤ ei ≤ n, 1 ≤ li+si−1 ≤ ui+si−1 ≤ 109), separated with spaces.
You should write m lines to output. Line number i should contain one integer si.
5 4 17 3 5 94 8 1 5 4 113 3 4 -2 0 2 5 2 93 2 2 0 0
4 0 3 1