시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB189555.376%

문제

최백준은 인화철도 구구칠에 탔다.

문제는 구구팔의 기장인 김재홍이 반쯤 미쳐서 열차의 대부분을 인화성 물질로 가득 채워놨다는 것이다.

그래서 불이 붙으면 꽝~하고 터져버린다. 꽝~하고 터지면 그 칸은 불이 사라지고, 좌우의 칸으로 불이 옮겨붙는다. 그러면 또 그 열차는 타다가 꽝~하고 터져버린다. 이런식으로 불은 번져나가게 된다. 각 열차칸은 여러 번 터질 수 있지만, 한 시각에는 한 번만 터질 수 있다. 예를 들어, 이전 시각에 2번 열차와 4번 열차에서 폭발이 일어났더라도, 다음 시각에 3번 열차에서는 한 번의 폭발만 일어난다.

만약 최백준이 타고 있는 열차칸이 타고 있다면 최백준을 태운 열차칸은 꽝~하고 터짐과 동시에 최백준을 태우게 된다.

그걸 방지하기 위해 반쯤만 미친 김재홍은 칸과 칸 사이에 발화 방지용 물질을 채워놓았다. 열차칸은 0~N번 칸까지 있으며, 0번째 칸과 1번째 칸 사이 역시 연결되어 있고, 이 둘 사이에는 발화 방지용 물질이 없다.

발화 방지용 물질은 왼쪽 또는 오른쪽에서 꽝 터져서 옮겨가는 것을 한번 막을 수 있다.

칸 사이의 발화 방지용 물질의 개수와 발화지점이 주어지면, 언제 최백준이 타고 있는 열차칸이 타서 폭발하게 되는지 출력하여라.

입력

첫째 줄에는 테스트 케이스의 개수 T(≤ 100)가 주어진다. 각각의 테스트 케이스는 n, k, c, 그리고 n-1개의 숫자로 이루어진다. k는 발화가 되는 지점(1-n중 한지점)이고, c는 최백준이 있는 지점이다. n-1개 숫자는 각각 순서대로 열차 칸 사이마다 막혀있는 발화 방지물질의 개수이다. n ≤ 1,000 이며, 주어지는 모든 수는 int범위이다.

출력

최백준이 타고있는 열차가 타서 폭발하는 시간을 출력한다. 만약 최백준이 타고 있는 열차가 폭발할 가능성이 없다면 “gg"을 출력한다.

예제 입력 1

2
5 1 1
1 2 1 3
5 2 3
0 1 0 0

예제 출력 1

0
3

출처

  • 빠진 조건을 찾은 사람: dotorya
  • 문제의 오타를 찾은 사람: jb_cubedr
  • 문제를 만든 사람: xhark