2418: Listening to Music
Time Limit: 2 Sec Memory Limit: 256 MBSubmit: 0 Solved: 0
[Submit] [Status] [Web Board] [Creator:]
Description
Please 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.
The 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.
Print exactly s integers ans1,ans2,...,anss, where ansi is the minimum displeasure that you can get on day i.
5 3
1 2 1 2 3
5
1 1 2
1 3 2
1 3 3
1 3 5
1 3 1
2
0
2
3
1