24393번 - 조커 찾기

문제

중앙대학교에 다니는 수현이는 머신러닝을 공부하던 중 심심하여 트럼프 카드를 가지고 놀고 있다. 언젠가 유튜브에서 타짜 기술을 사용하는 영상을 보고 따라하고 싶어진 수현이는 카드 덱의 맨 위에 조커를 올려두고 카드를 섞어서 원하는 위치로 보내고자 한다.

카드는 일반 카드 26장, 조커 1장 총 27장을 사용한다. 맨 위쪽 카드를 1번, 맨 아래쪽 카드를 27번이라고 하자.

처음 상태에선 조커가 1번 위치에 있다.

카드 섞기를 N번 진행한다고 할 때 i번째로 카드를 섞는 방법을 A_i라고 한다면,

i번째 새로운 덱은 다음과 같은 순서로 만들어진다.

1. i-1번째 덱의 위에서부터 순서를 유지한 채로 13장을 왼쪽으로, 나머지 14장을 오른쪽으로 가져간다.
2. 오른쪽 덱의 맨 위에서 A_i1장을 가져와서 새로운 덱의 맨 위에 배치한다.
3. 왼쪽 덱의 맨 위에서 A_i2장을 가져와서 그 아래에 배치한다.
4. 다시 남은 오른쪽 덱의 맨 위에서 A_i3장을 가져와 3번에서 만든 덱 아래에 배치한다.
5. 3~4번과 같이 A_ij장씩을 교대로 가져와서 새로운 덱 아래에 배치한다. 단, A_i홀수의 합은 14, A_i짝수의 합은 13이다. 즉, A_i의 합은 27이다.

이 기술을 사용할 줄 모르는 수현이를 위해 카드를 섞은 횟수와 섞일 때마다 카드가 어떻게 섞이는지 주어진다면, 카드 섞기를 마치고 난 후 조커의 위치는 위에서부터 몇 번째 카드인지 알려주자!

입력

첫 번째 줄에는 카드를 섞는 횟수 N이 주어진다. (1 ≤ N ≤ 10⁶)

두 번째 줄부터 N+1번째 줄까지 각 줄마다 i번째 새로운 덱을 만들기 위해 수열 A_i가 주어진다. (1 ≤ i ≤ N, 1 ≤ A_ij​)

입력되는 모든 정수의 개수는 10⁷ + 1개 이하이다.

출력

카드 섞기를 완료했을 때 조커가 덱의 맨 위에서 몇 번째에 있는지 출력한다.

제한

힌트

이 문제는 매우 많은 입력을 요구합니다. 입력단에서 시간 초과를 방지하기 위해 여기를 참고해주시길 바랍니다.

또한 주요 언어별 빠른 입력은 아래의 코드를 활용하시면 됩니다.

• C++:
  • cin.tie(NULL);
  • cin.sync_with_stdio(false);
• Java:
  • BufferedReader
  • Integer.parseInt
• Python:
  • sys.stdin.readline()