题目描述

有 $n$ 盏灯环形排列，顺时针依次标号为 $1\cdots n$。初始时刻为 $0$，初始时刻第 $i$ 盏灯的亮灭 $a_i$ 给定，$0$ 表示灭，$1$ 表示亮。下一时刻每盏灯的亮灭取决于当前时刻这盏灯与顺时针方向下一盏灯的亮灭。若两盏灯状态相同，则下一时刻该灯灭，否则该灯亮。

试求时刻 $t$ 第 $k$ 盏灯的状态。

输入格式

第一行，三个整数，分别为 $n, t, k$。

第二行，共 $n$ 个整数，分别为 $0$ 或 $1$，代表 $a_i$。

输出格式

共一行，一个数，$0$ 或 $1$，代表时刻 $t$ 第 $k$ 盏灯的状态。

4 2 1
1 0 1 0

0

提示

• 对于 $25\%$ 的数据，有$1\leq t, k\leq n\leq 1000$。
• 对于 $60\%$ 的数据，有$1\leq t, k\leq n\leq 10^5$。
• 对于 $100\%$ 的数据，有$1\leq t, k\leq n\leq 3\times 10^6$。