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 $*a*_{*i*}$.

On the $*i*$-th day you choose some integer $*v*$ ($*l*_{*i*} ≤ *v* ≤ *r*_{*i*}$) and listen to songs number $*v*, *v* + 1, ..., *v* + *m* - 1$. On the $*i*$-th day listening to one song with quality less than $*q*_{*i*}$ 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·10^{5}$). The second line contains $*n*$ positive integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ ($0 ≤ *a*_{*i*} < 2^{30}$) — the description of songs from the playlist.

The next line contains a single number $*s*$ ($1 ≤ *s* ≤ 2·10^{5}$) — the number of days that you consider.

The next $*s*$ lines contain three integers each $*l*_{*i*}, *r*_{*i*}, *x*_{*i*}$ ($1 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ *n* - *m* + 1$; $0 ≤ *x*_{*i*} < 2^{30}$) — the description of the parameters for the $*i*$-th day. In order to calculate value $*q*_{*i*}$, you need to use formula: , where $*ans*_{*i*}$ is the answer to the problem for day $*i*$. Assume that $*ans*_{0} = 0$.

Output

Print exactly $*s*$ integers $*ans*_{1}, *ans*_{2}, ..., *ans*_{*s*}$, where $*ans*_{*i*}$ is the minimum displeasure that you can get on day $*i*$.