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⁵). The second line contains n positive integers a₁, a₂, ..., a_n (0 ≤ a_i < 2³⁰) — the description of songs from the playlist.

The next line contains a single number s (1 ≤ s ≤ 2·10⁵) — 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³⁰) — the description of the parameters for the i-th day. In order to calculate value q_i, you need to use formula: $\text{[math]}$ , where ans_i is the answer to the problem for day i. Assume that ans₀ = 0.

Output

Print exactly s integers ans₁, ans₂, ..., ans_s, where ans_i is the minimum displeasure that you can get on day i.

Listening to Music

Examples