Description

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.

Input Format

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 Format

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

10 3
1 1 2 2 3 5 3 2 1 3

5

13 4
1 1 4 5 1 4 1 4 4 5 5 5 1

1

Hint

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:

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<='9')
    ret=ret*10+c-'0';
    return ret*w;
}

Or use this template:

typedef long long LL;
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
static char buf[100000],*pa(buf),*pb(buf);
inline LL readint() {
	LL x=0;char c=gc;
	while(c<'0'||c>'9')c=gc;
	for(;c>='0'&&c<='9';c=gc)x=x*10+(c&15);
	return x;
}

With the O2 switch enabled, on the largest testdata, the former takes $500\texttt{ms}$ for input, while the latter needs $300\texttt{ms}$. That is, your program has at least $500\sim 700\texttt{ms}$ to run the main algorithm.

Translated by ChatGPT 5