{"raw_statement":[{"iden":"statement","content":"Once, Leha found in the left pocket an array consisting of _n_ integers, and in the right pocket _q_ queries of the form _l_ _r_ _k_. If there are queries, then they must be answered. Answer for the query is minimal _x_ such that _x_ occurs in the interval _l_ _r_ strictly more than times or  - 1 if there is no such number. Help Leha with such a difficult task."},{"iden":"input","content":"First line of input data contains two integers _n_ and _q_ (1 ≤ _n_, _q_ ≤ 3·105) — number of elements in the array and number of queries respectively.\n\nNext line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ _n_) — Leha's array.\n\nEach of next _q_ lines contains three integers _l_, _r_ and _k_ (1 ≤ _l_ ≤ _r_ ≤ _n_, 2 ≤ _k_ ≤ 5) — description of the queries."},{"iden":"output","content":"Output answer for each query in new line."},{"iden":"examples","content":"Input\n\n4 2\n1 1 2 2\n1 3 2\n1 4 2\n\nOutput\n\n1\n-1\n\nInput\n\n5 3\n1 2 1 3 2\n2 5 3\n1 2 3\n5 5 2\n\nOutput\n\n2\n1\n2"}],"translated_statement":[{"iden":"statement","content":"有一次，Leha 在左口袋发现了一个包含 $n$ 个整数的数组，在右口袋发现了一个包含 $q$ 个形如 $l$ $r$ $k$ 的查询。如果有查询，则必须回答。每个查询的答案是满足在区间 $[l, r]$ 中出现次数严格大于 $\\frac{r - l + 1}{k}$ 次的最小的 $x$，如果不存在这样的数，则输出 $-1$。请帮助 Leha 解决这个难题。\n\n输入数据的第一行包含两个整数 $n$ 和 $q$（$1 ≤ n, q ≤ 3·10^5$）——数组的元素个数和查询个数。\n\n下一行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ n$）——Leha 的数组。\n\n接下来的 $q$ 行每行包含三个整数 $l$, $r$ 和 $k$（$1 ≤ l ≤ r ≤ n$, $2 ≤ k ≤ 5$）——查询的描述。\n\n请在每行输出每个查询的答案。\n\n"},{"iden":"input","content":"输入数据的第一行包含两个整数 $n$ 和 $q$（$1 ≤ n, q ≤ 3·10^5$）——数组的元素个数和查询个数。下一行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ n$）——Leha 的数组。接下来的 $q$ 行每行包含三个整数 $l$, $r$ 和 $k$（$1 ≤ l ≤ r ≤ n$, $2 ≤ k ≤ 5$）——查询的描述。"},{"iden":"output","content":"请在每行输出每个查询的答案。"},{"iden":"examples","content":"输入\n4 2\n1 1 2 2\n1 3 2\n1 4 2\n输出\n1\n-1\n\n输入\n5 3\n1 2 1 3 2\n2 5 3\n1 2 3\n5 5 2\n输出\n2\n1\n2"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the size of the array and number of queries, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be an array of integers where $ a_i \\in \\{1, 2, \\dots, n\\} $.  \nFor each query $ j \\in \\{1, \\dots, q\\} $, let $ (l_j, r_j, k_j) $ denote the query parameters, where $ 1 \\le l_j \\le r_j \\le n $ and $ 2 \\le k_j \\le 5 $.\n\n**Constraints**  \n1. $ 1 \\le n, q \\le 3 \\cdot 10^5 $  \n2. $ 1 \\le a_i \\le n $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. For each query $ j $:  \n   - $ 1 \\le l_j \\le r_j \\le n $  \n   - $ 2 \\le k_j \\le 5 $\n\n**Objective**  \nFor each query $ j $, define the subarray $ A_{[l_j, r_j]} = (a_{l_j}, a_{l_j+1}, \\dots, a_{r_j}) $.  \nLet $ f_j(x) $ denote the frequency of value $ x $ in $ A_{[l_j, r_j]} $.  \n\nCompute:  \n$$\n\\text{ans}_j = \\min \\left\\{ x \\in \\mathbb{Z}^+ \\mid f_j(x) > k_j \\right\\}\n$$  \nif such an $ x $ exists; otherwise, $ \\text{ans}_j = -1 $.","simple_statement":null,"has_page_source":false}