{"raw_statement":[{"iden":"statement","content":"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 .\n\nFirst 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.\n\nQ lines, each containing the answer to one query.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"Q lines, each containing the answer to one query."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, Q \\in \\mathbb{Z}^+ $.  \nLet $ A = (a_1, a_2, \\dots, a_N) $ and $ B = (b_1, b_2, \\dots, b_N) $ be two arrays of integers.  \nLet $ \\mathcal{Q} = \\{(i_q, j_q, k_q) \\mid q \\in \\{1, \\dots, Q\\}\\} $ be the set of queries.\n\n**Constraints**  \n1. $ 1 \\leq N, Q \\leq 10^5 $  \n2. $ 1 \\leq a_i, b_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, N\\} $  \n3. For each query $ q $:  \n   - $ 1 \\leq i_q \\leq j_q \\leq N $  \n   - $ 1 \\leq k_q \\leq 10^5 $\n\n**Objective**  \nFor each query $ (i, j, k) \\in \\mathcal{Q} $, compute the cardinality of the multiset:  \n$$\n\\{ a_\\ell \\mid \\ell \\in \\{i, i+1, \\dots, j\\} \\} \\cap \\{ b_\\ell \\mid \\ell \\in \\{i, i+1, \\dots, j\\} \\}\n$$  \ni.e., the number of elements that appear in both subarrays $ A[i:j] $ and $ B[i:j] $, counting multiplicities.","simple_statement":"Given two arrays A and B of size N, and Q queries.  \nFor each query (i, j, k), count how many times the value k appears in the multiset { A[i] + B[i], A[i+1] + B[i+1], ..., A[j] + B[j] }.","has_page_source":false}