403169: GYM101059 D Impressive Queries

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 .

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

Q lines, each containing the answer to one query.

5 1
1 1 1 1 1
1 1 1 1 1
1 5 1

25