Description

There are $n$ lamps arranged in a circle, labeled clockwise as $1 \cdots n$. The initial time is $0$. At the initial time, the on/off state $a_i$ of the $i$-th lamp is given, where $0$ means off and $1$ means on. At the next time, each lamp’s state depends on the current state of this lamp and the next lamp in the clockwise direction. If the two lamps have the same state, then at the next time this lamp is off; otherwise, it is on.

Find the state of the $k$-th lamp at time $t$.

Input Format

The first line contains three integers $n$, $t$, $k$.

The second line contains $n$ integers, each being $0$ or $1$, representing $a_i$.

Output Format

Output one line with a single number, $0$ or $1$, representing the state of the $k$-th lamp at time $t$.

4 2 1
1 0 1 0

0

Hint

• For $25\%$ of the testdata, $1 \leq t, k \leq n \leq 1000$.
• For $60\%$ of the testdata, $1 \leq t, k \leq n \leq 10^5$.
• For $100\%$ of the testdata, $1 \leq t, k \leq n \leq 3 \times 10^6$.

Translated by ChatGPT 5