P6306 “Wdsr-1” Kosuzu’s Books

Motoori Kosuzu runs a bookstore called “Suzunaan” in the Human Village. The shop is neatly stocked with a huge number of books. One day, Marisa came to Suzunaan to borrow books and made a big mess. The grimoire Marisa carried and the books in Suzunaan were all mixed together.

Kosuzu has a total of $n-1$ books. Each book has an ID number $a_i$. Two books belong to the same category if and only if their ID numbers are the same. Because Kosuzu usually keeps the books well organized, among her $n-1$ books, the count of books in every category is exactly a multiple of $k$, where $k$ is a given constant. Now, one grimoire of Marisa with an unknown ID number is mixed into Kosuzu’s $n-1$ books. Marisa can only retrieve it if she knows the ID number of the grimoire. Since there are too many books, Marisa asks you for help, hoping you can find the ID number of the grimoire that got mixed in. **Note: Marisa’s grimoire may have the same ID number as one of Kosuzu’s books.**

The first line contains two integers $n, k$, with the same meaning as in the statement. It is guaranteed that $n\equiv 1 \pmod k$. The second line contains $n$ integers, representing the ID numbers $a_i$ of the $n$ books after being mixed together.

Output one integer in a single line, representing the ID number of Marisa’s grimoire.

#### Sample Explanation In sample $1$, Kosuzu’s book ID numbers are $1, 2, 3$, and each appears $3$ times. Therefore, the grimoire’s ID number is $5$. In sample $2$, Kosuzu’s book ID numbers are $1, 4, 5$, and each appears $4$ times. Therefore, the grimoire’s ID number is $1$. ------------------------ #### Constraints and Notes **This problem uses bundled testdata.** $$ \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{Score} \cr\hline 1 & 10^5 & 50 \cr\hline 2 & 10^6 & 25 \cr\hline 3 & 10^7 & 25 \cr\hline \end{array} $$ For all data, it is guaranteed that $1 \le n \le 10^7$, $2 \le k \le 10^3$, and $1 \le a_i \le 10^{18}$. The input is guaranteed to be valid, meaning there is one and only one mixed-in grimoire. ----------------- #### Hint **Please pay attention to the time and memory limits.** **Using $\texttt{cin}$ / $\texttt{cout}$ may cause TLE. Here is a fast input template:** ```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