E. Listening to Musictime limit per test7 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard outputPlease note that the memory limit differs from the standard.You really love to listen to music. During the each of next s days you will listen to exactly m songs from the playlist that consists of exactly n songs. Let's number the songs from the playlist with numbers from 1 to n, inclusive. The quality of song number i is ai.On the i-th day you choose some integer v (li ≤ v ≤ ri) and listen to songs number v, v + 1, ..., v + m - 1. On the i-th day listening to one song with quality less than qi increases your displeasure by exactly one.Determine what minimum displeasure you can get on each of the s next days. InputThe first line contains two positive integers n, m (1 ≤ m ≤ n ≤ 2·105). The second line contains n positive integers a1, a2, ..., an (0 ≤ ai < 230) — the description of songs from the playlist. The next line contains a single number s (1 ≤ s ≤ 2·105) — the number of days that you consider.The next s lines contain three integers each li, ri, xi (1 ≤ li ≤ ri ≤ n - m + 1; 0 ≤ xi < 230) — the description of the parameters for the i-th day. In order to calculate value qi, you need to use formula: , where ansi is the answer to the problem for day i. Assume that ans0 = 0. OutputPrint exactly s integers ans1, ans2, ..., anss, where ansi is the minimum displeasure that you can get on day i.ExamplesInput5 31 2 1 2 351 1 21 3 21 3 31 3 51 3 1Output20231
Input5 31 2 1 2 351 1 21 3 21 3 31 3 51 3 1
Output20231
['constructive algorithms', 'data structures', '*3200']