在 Reme 正在举行一场领事选举。这次选举共有 $N$ 名选民，每名选民可以从 $1\,000\,000\,000$ 名候选人中选择一人投票。如果一名候选人的得票数严格超过总票数的三分之一，则该候选人被视为获胜者（这是因为 Reme 每年选出两名领事）。现在，你是一名渴望操纵选举的人。为了更有效地操纵投票，你需要知道至少一名潜在的获胜者。不幸的是，尽管每位选民都已经投了票，但投票结果并不公开——至少在没有付出代价的情况下是不公开的。此外，已经统计过选票的旧领事可以告诉你特定候选人获得的票数——同样，这需要付出代价。

更正式地说，你需要考虑一个包含 $N$ 个整数的隐藏序列 $v[1] \dots v[N]$，其值至少为 $0$ 且小于 $1\,000\,000\,000$。你可以对该序列执行两种类型的查询： 你可以查出序列中特定元素 $v[i]$ 的值。 你可以查看特定值 $x$ 在序列中出现的次数。

你需要找到一个在序列中出现次数严格大于 $N/3$ 的值 $x$，同时使你执行的查询次数尽可能少。

题目描述

给定 $N$，使用给定的查询找出选举的任意一名获胜者，或者宣布不存在获胜者。

交互

这是一道交互题。选手需要包含头文件 grader.h 并实现函数 void solve(int N)，其中参数 $N$ 代表题目描述中的 $N$。该函数需要解决一个任务实例（注意：在一次程序运行中，该函数可能会被调用多次）。为了解决任务，选手可以使用以下函数：

• int kth(int i) — 返回 $v[i]$ 的值。
• int cnt(int x) — 返回 $x$ 在数组 $v$ 中的出现频率。
• void say_answer(int a) — 如果 $a$ 在 $0$ 到 $1\,000\,000\,000 - 1$ 之间，则表示 $a$ 是选举的获胜者；如果 $a$ 为 $-1$，则表示不存在获胜者。如果存在获胜者但 $a$ 不是获胜者，或者不存在获胜者但 $a$ 不为 $-1$，或者 $a$ 既不是有效的候选人也不是 $-1$，则选手的程序将获得“Wrong Answer!”判决。

数据范围

评分

设 $Q$ 为单个测试文件中任意测试用例中执行的最大查询次数（不包括 say_answer 的调用）。

子任务 1： 如果 $Q \le 50$，你将获得该测试用例 100% 的分数。 如果 $Q > 50$，你将获得该测试用例 0% 的分数。

子任务 2： 如果 $Q \le 60$，你将获得该测试用例 100% 的分数。 如果 $60 < Q \le 110$，你将获得 $(220-2Q)\%$ 的分数。 * 如果 $Q > 100$，你将获得该测试用例 0% 的分数。

子任务 3： 如果 $Q \le 60$，你将获得该测试用例 100% 的分数。 如果 $60 < Q$，你将获得 $(0.9^{Q - 60} \times 100)\%$ 的分数。

说明：测试用例数量最多为 16000。