5225: Listening to Music
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
E. Listening to Music
time limit per test
7 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output
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.
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.
Input
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 descThe 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 desc
, where ansi is the answer to the problem for day i. Assume that ans0=0.
Output
Print exactly s integers ans1,ans2,...,anss, where ansi is the minimum displeasure that you can get on day i.
Examples
Input
5 3 1 2 1 2 3 5 1 1 2 1 3 2 1 3 3 1 3 5 1 3 1
Output
2 0 2 3 1
输入样例 复制
输出样例 复制