{"raw_statement":[{"iden":"statement","content":"As you might remember from our previous rounds, Vova really likes computer games. Now he is playing a strategy game known as Rage of Empires.\n\nIn the game Vova can hire _n_ different warriors; _i_th warrior has the type _a__i_. Vova wants to create a _balanced_ army hiring some subset of warriors. An army is called _balanced_ if for each type of warrior present in the game there are not more than _k_ warriors of this type in the army. Of course, Vova wants his army to be as large as possible.\n\nTo make things more complicated, Vova has to consider _q_ different plans of creating his army. _i_th plan allows him to hire only warriors whose numbers are not less than _l__i_ and not greater than _r__i_.\n\nHelp Vova to determine the largest size of a _balanced_ army for each plan.\n\n**Be aware that the plans are given in a modified way. See input section for details.**"},{"iden":"input","content":"The first line contains two integers _n_ and _k_ (1 ≤ _n_, _k_ ≤ 100000).\n\nThe second line contains _n_ integers _a_1, _a_2, ... _a__n_ (1 ≤ _a__i_ ≤ 100000).\n\nThe third line contains one integer _q_ (1 ≤ _q_ ≤ 100000).\n\nThen _q_ lines follow. _i_th line contains two numbers _x__i_ and _y__i_ which represent _i_th plan (1 ≤ _x__i_, _y__i_ ≤ _n_).\n\nYou have to keep track of the answer to the last plan (let's call it _last_). In the beginning _last_ = 0. Then to restore values of _l__i_ and _r__i_ for the _i_th plan, you have to do the following:\n\n1.  _l__i_ = ((_x__i_ + _last_) _mod_ _n_) + 1;\n2.  _r__i_ = ((_y__i_ + _last_) _mod_ _n_) + 1;\n3.  If _l__i_ > _r__i_, swap _l__i_ and _r__i_."},{"iden":"output","content":"Print _q_ numbers. _i_th number must be equal to the maximum size of a _balanced_ army when considering _i_th plan."},{"iden":"example","content":"Input\n\n6 2\n1 1 1 2 2 2\n5\n1 6\n4 3\n1 1\n2 6\n2 6\n\nOutput\n\n2\n4\n1\n3\n2"},{"iden":"note","content":"In the first example the real plans are:\n\n1.  1 2\n2.  1 6\n3.  6 6\n4.  2 4\n5.  4 6"}],"translated_statement":[{"iden":"statement","content":"正如你在我们之前的比赛中所记得的，Vova 非常喜欢电子游戏。现在他正在玩一款名为《帝国怒火》的战略游戏。\n\n在游戏中，Vova 可以雇佣 #cf_span[n] 名不同的战士；第 #cf_span[i] 名战士的类型为 #cf_span[ai]。Vova 希望通过选择一部分战士来组建一支 _平衡_ 的军队。一支军队被称为 _平衡_ 的，是指对于游戏中存在的每种战士类型，军队中该类型的战士数量不超过 #cf_span[k]。当然，Vova 希望他的军队尽可能大。\n\n为了使事情更加复杂，Vova 必须考虑 #cf_span[q] 种不同的组建军队方案。第 #cf_span[i] 种方案只允许他雇佣编号不小于 #cf_span[li] 且不大于 #cf_span[ri] 的战士。\n\n请帮助 Vova 确定每种方案下 _平衡_ 军队的最大规模。\n\n*请注意，这些方案是以修改后的形式给出的。详情请参见输入部分。*\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n, k ≤ 100000])。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ... #cf_span[an] (#cf_span[1 ≤ ai ≤ 100000])。\n\n第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100000])。\n\n接下来 #cf_span[q] 行，每行包含两个数字 #cf_span[xi] 和 #cf_span[yi]，表示第 #cf_span[i] 种方案 (#cf_span[1 ≤ xi, yi ≤ n])。\n\n你必须记录上一个方案的答案（记作 #cf_span[last]）。初始时 #cf_span[last = 0]。为了恢复第 #cf_span[i] 种方案的 #cf_span[li] 和 #cf_span[ri] 值，你需要执行以下操作：\n\n请输出 #cf_span[q] 个数字。第 #cf_span[i] 个数字必须等于考虑第 #cf_span[i] 种方案时 _平衡_ 军队的最大规模。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n, k ≤ 100000])。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ... #cf_span[an] (#cf_span[1 ≤ ai ≤ 100000])。第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100000])。接下来 #cf_span[q] 行，每行包含两个数字 #cf_span[xi] 和 #cf_span[yi]，表示第 #cf_span[i] 种方案 (#cf_span[1 ≤ xi, yi ≤ n])。你必须记录上一个方案的答案（记作 #cf_span[last]）。初始时 #cf_span[last = 0]。为了恢复第 #cf_span[i] 种方案的 #cf_span[li] 和 #cf_span[ri] 值，你需要执行以下操作：\n\n#cf_span[li = ((xi + last) mod n) + 1];\n#cf_span[ri = ((yi + last) mod n) + 1];\n如果 #cf_span[li > ri]，则交换 #cf_span[li] 和 #cf_span[ri]。"},{"iden":"output","content":"请输出 #cf_span[q] 个数字。第 #cf_span[i] 个数字必须等于考虑第 #cf_span[i] 种方案时 _平衡_ 军队的最大规模。"},{"iden":"note","content":"在第一个例子中，真实的方案是：\n\n#cf_span[1 2]\n#cf_span[1 6]\n#cf_span[6 6]\n#cf_span[2 4]\n#cf_span[4 6]"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $, $ A = (a_1, a_2, \\dots, a_n) $ with $ a_i \\in \\mathbb{Z}^+ $, $ q \\in \\mathbb{Z}^+ $.  \nLet $ \\text{last} = 0 $ initially. For each plan $ i \\in \\{1, \\dots, q\\} $, given $ (x_i, y_i) $, compute:  \n$$\nl_i = ((x_i + \\text{last}) \\bmod n) + 1, \\quad r_i = ((y_i + \\text{last}) \\bmod n) + 1\n$$  \nThen let $ L_i = \\min(l_i, r_i) $, $ R_i = \\max(l_i, r_i) $.  \n\n**Constraints**  \n1. $ 1 \\le n, k \\le 100000 $  \n2. $ 1 \\le a_i \\le 100000 $  \n3. $ 1 \\le q \\le 100000 $  \n4. $ 1 \\le x_i, y_i \\le n $  \n\n**Objective**  \nFor each plan $ i \\in \\{1, \\dots, q\\} $, compute the maximum size of a balanced army over the subarray $ A[L_i:R_i] $, where a balanced army satisfies:  \n- For each warrior type $ t $, the count of warriors of type $ t $ in the army is at most $ k $.  \n- The army is a subset of warriors in positions $ \\{L_i, L_i+1, \\dots, R_i\\} $.  \n\nThat is, for each plan $ i $, compute:  \n$$\n\\max \\left\\{ \\sum_{t} \\min(c_t, k) \\,\\middle|\\, c_t = \\left| \\{ j \\in [L_i, R_i] : a_j = t \\} \\right| \\right\\}\n$$","simple_statement":null,"has_page_source":false}