D. Impressive Queries
time limit per test
10 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You are given two arrays, A and B, both of size N. You are given Q queries of the form (i, j, k). Where for each query, you have to find the cardinality of the multiset .

Input

First line contains two integers, N, and Q (1 ≤ N, Q ≤ 105). The next line contains N integers, the array A (1 ≤ Ai ≤ 109). The next line contains N integers, the array B (1 ≤ Bi ≤ 109). Each of the next Q lines contains three integers, i, j and k (1 ≤ i ≤ j ≤ N, 1 ≤ K ≤ 105), which represent a query as defined in the statement.

Output

Q lines, each containing the answer to one query.

Example
Input
5 1
1 1 1 1 1
1 1 1 1 1
1 5 1
Output
25