F. Armed Soldiers 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are two independent parts of this problem. The common part is highlighted in italics.

There are $$$n$$$ soldiers positioned at locations $$$a_i$$$, each armed with a gun of power $$$p_i$$$.

Whenever they spot a monster with a shield with $$$s$$$ standing at location $$$d$$$, each soldier fires a bullet towards it. The bullet starts with an initial effective power of $$$p_i$$$, but due to air resistance, this power decreases by 1 for every unit the bullet travels.

The Bullet will hit the monster if the effective power is greater than or equal to the shield width. Then let the number of bullets that hit the monster be $$$c(d,s)$$$

Formally, let $$$c(d,s)$$$ be the number of $$$1 \leq i\leq n$$$ such that $$$|a_i - d| \leq p_i - s$$$.

You are given $$$q$$$ queries for each query compute $$$\sum_{d=l}^r c(d, s)$$$

Input

The first line contains two integers $$$n \:(1\leq n \leq 10^6)$$$ and $$$q \:(1\leq q \leq 10^6)$$$.

The second line contains $$$n$$$ integers $$$a_i \:(1\leq a_i \leq 2\times 10^3)$$$ denoting the location of the $$$i^{\mathrm{th}}$$$ soldier.

The third line contains $$$n$$$ integers $$$p_i \:(0\leq p_i \leq 10^3)$$$ denoting the power of the $$$i^{\mathrm{th}}$$$ soldier.

For the next $$$q$$$ lines, each line contains three integers $$$l\:(1\leq l \leq 2\times 10^3)$$$, $$$r\:(l\leq r \leq 2\times 10^3)$$$ and $$$s \:(1\leq s \leq 10^3)$$$ denoting the location of the monster and the shield width for that day.

Clarification: The shield width must be a non-negative integer, the position of the monster must be an integer.

Output

For each query, print a single integer, the sum of the number of bullets that hit the monsters.

Example
Input
5 3
3 4 3 6 5
0 1 1 2 3
2 5 1
2 4 2
2 6 1
Output
6
1
8
Note

$$$c(3, 1) = 2$$$, $$$\because (i = 3, 5)$$$ satisfy the above inequality

Similarly, $$$c(2, 1) = 0$$$, $$$c(4, 1) = 2$$$, $$$c(5,1) = 2$$$

$$$\sum_{d=2}^5 c(d, 1) = 6$$$