P6306 「Wdsr-1」小铃的书
题目背景
本居小铃在人间之里经营着一家名为“铃奈庵”的书店。店里井井有条地堆放着很多很多书。
一天,魔理沙来铃奈庵借书,搞得店里十分混乱,魔理沙随身携带的魔导书与铃奈庵的书籍全都混在了一起。
题目描述
小铃一共有 $n-1$ 本书,每本书有一个编号 $a_i$,两本书属于同一种类当且仅当两本书的编号相同。
由于小铃平时将这些书整理得井井有条,因此在小铃的 $n-1$ 本书中,每个种类的书的数量都恰好是 $k$ 的倍数,其中 $k$ 是一给出的常数。
现在,魔理沙的一本编号未知的魔导书与小铃的 $n-1$ 本书混在了一起,而魔理沙只有知道魔导书的编号才能将其找回。
由于书的数量实在太多,魔理沙找到了你来帮忙,希望聪明的你能帮她求出混入的魔导书的编号。
**注意:魔理沙的魔导书可能与小铃的某本书有着相同的编号。**
输入格式
无
输出格式
无
说明/提示
#### 样例说明
样例 $1$ 中,小铃的书的编号为 $1,2,3$,分别有 $3$ 本。因此魔导书的编号为 $5$。
样例 $2$ 中,小铃的书的编号为 $1,4,5$,分别有 $4$ 本。因此魔导书的编号为 $1$。
------------------------
#### 数据范围及约定
**本题采取捆绑测试。**
$$
\def\arraystretch{1.5}
\def\cuteran{https://www.luogu.com.cn/paste/iyzwht7l}
\begin{array}{|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le} & \textbf{分值} \cr\hline
1 & 10^5 & 50 \cr\hline
2 & 10^6 & 25 \cr\hline
3 & 10^7 & 25 \cr\hline
\end{array}
$$
对于全部数据,保证 $1 \le n \le 10^7$ ,$2 \le k \le 10^3$ ,$1 \le a_i \le 10^{18}$。保证数据合法,即有且只有一本混入的魔导书。
-----------------
#### 提示
**请注意时空限制。**
**使用 $\texttt{cin}$ / $\texttt{cout}$ 可能超时,这里给出一个快速读入模板:**
```cpp
long long qread(){
long long w=1,c,ret;
while((c=getchar())> '9'||c< '0')
w=(c=='-'?-1:1); ret=c-'0';
while((c=getchar())>='0'&&c='0'&&c