题目描述

一个饭店怎么能没有自己的特色菜呢,于是阿什尼决定出去寻找美味的食材.但是在路程中不小心进入了一个陷阱:回旋迷宫

回旋迷宫由$n$个门组成,这些门围成一圈.阿什尼给这些门按顺时针编号为$0,1,2,3,\cdots,n-1$.任意两个相邻的门之间的距离为$1$,阿什尼由$now$号门不小心进入迷宫.

但是不用担心,阿什尼已经找出了走出迷宫的方法，进行$p$次行走，第$i$次行走沿当前的前进方向到他距离$a_i$的门停止，但是每$k$行走后，阿什尼都需要改变一下前进的方向. 如他将在第$1$到 $k$ 轮沿顺时针方向前进，在第 $k+1$到 $2 \tiems k$ 轮沿逆时针方向旅行,在第 $2 \times k+1$到第 $3 \times k$ 轮再沿顺时针方向前进...依次递推，直到他完成了$p$轮行走后,停下来的那个门就是出品。(阿什尼第一轮一定沿顺时针前进）

阿什尼想知道,按这个方法,他最后可以从哪个门出去.

输入格式

第一行四个由空格隔开的整数，依次表示 $n,p,k,now$意义见题面描述.

接下来一行为 $p$ 个由空格隔开的数字，第 $i$ 个数字代表 $a_i$，意义见题面描述。

输出格式

一个整数，表示阿什尼 $p$ 轮后所在门的编号。

样例输入1

1000 3 2 10
1 3 2

样例输出1

12

数据范围与提示

对于 $40\%$ 的测试数据，$p \leq k$。

对于 $100\%$ 的测试数据，$n,p,k,now$ 以及所有的 $a_i$ 均为大等于零且小于10000的整数。

样例解释:

阿什尼初始在第 $10$ 号门，共需进行 $3$ 轮旅行，每两轮变换一次方向。

• 第一轮，阿什尼沿顺时针到距离 $10$ 号门为 $1$ 的门，到达 $11$ 号门。
• 第二轮，阿什尼沿顺时针到距离 $11$ 号门为 $3$ 的门，到达 $14$ 号门。
• 第三轮，阿什尼变换方向，沿逆时针到距离 $14$ 号门为 $2$ 的门，到达 $12$ 号门。