Монокарп только что выучил новый карточный фокус, и ему не терпится его вам показать. Он показывает вам всю колоду из \(n\) карт. Вы видите, что значения на картах от самой верхней к самой нижней — это целые числа \(a_1, a_2, \dots, a_n\), и все значения различны.
Затем он просит вас перемешать колоду \(m\) раз. На \(j\)-м перемешивании вы должны взять \(b_j\) карт сверху колоды и переместить их под оставшиеся \((n - b_j)\) карт, не меняя порядка ни в одной из частей.
Затем с помощью какой-то магии Монокарп называет вам карту на вершине колоды. Однако, вы не очень-то верите в его магию. Вы утверждаете, что знаете карту на вершине колоды и сами. Можете ли вы удивить Монокарпа и назвать ему карту на вершине колоды до того, как он покажет ее вам?
Выходные данные
На каждый набор входных данных выведите одно целое число — значение карты на вершине колоды после \(m\) перемешиваний.
Примечание
В первом наборе входных данных каждое перемешивание по факту меняет местами две карты. После трех перемешиваний колода примет вид \([2, 1]\).
Во втором наборе входных данных второе перемешивание отменяет действие первого. Сначала три верхние карты перемещаются под последнюю карту, затем эта карта перемещается обратно под оставшиеся три карты. Поэтому колода остается неизменна от начальной — на ее вершине карта со значением \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1 2
3
1 1 1
4
3 1 4 2
2
3 1
5
2 1 5 4 3
5
3 2 1 2 1
|
2
3
3
|