31909번 - FOCUS 서브태스크

문제

한 공장에서 인공지능 로봇이 오작동을 일으켜 폭주하고 있다. 로봇의 작동을 멈추기 위해서는 주어진 8ドル$개의 키 중 어느 것이 로봇을 정지시키는 키인지 찾아야 한다. 그러나 로봇이 그 키마저도 섞기 시작했다. 섞는 속도가 매우 빨라 인간의 시력으로는 키의 움직임을 추적할 수 없다. 다행히 당신은 로봇이 키를 섞는 데 사용하는 알고리즘과 로봇을 정지시키는 키의 처음 위치를 알고 있다.

각 키에는 0ドル$번부터 7ドル$번까지의 번호가 매겨져 있고, 이들은 각각 서로 다른 점 $P_0, P_1, \cdots, P_7$ 위에 놓여 있다. 로봇은 미리 주어진 길이 $N$의 수열을 하나씩 순서대로 읽으며 키를 섞는다. 이때 $i$번 키와 $j$번 키$(i < j)$의 위치를 바꾸는 명령은 정수 2ドル^i + 2^j$로 인코딩된다. $i$번 키와 $j$번 키의 위치를 바꾼다는 것은, $i$번 키가 점 $P_k$에 놓여 있고 $j$번 키가 점 $P_l$에 놓여 있을 때 $i$번 키를 점 $P_l$ 위치로 옮기고 $j$번 키를 점 $P_k$ 위치로 옮긴다는 것이다.

로봇이 읽는 수열 안에는 유효하지 않은 명령도 존재할 수 있다. 유효하지 않은 명령 $x$는 어떤 두 정수 $i, j(0 \leq i < j \leq 7)$에 대해서도 $x = 2^i + 2^j$를 만족시키지 않는 명령이다. 로봇이 유효하지 않은 명령을 인식하면 그 명령을 무시하고 다음 명령으로 넘어간다.

로봇을 정지시키는 키의 번호와 명령들의 수열이 주어지면, 로봇을 정지시키는 키는 $P_0, P_1, \cdots, P_7$ 중 몇 번 점에 위치하는지 구하시오.

입력

첫째 줄에 로봇이 읽는 명령들의 수열의 길이 $N$이 주어진다. (1ドル \leq N \leq 200,000円$)

둘째 줄에 로봇이 읽는 명령들의 수열 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다. (0ドル \leq a_i < 256=2^8$)

셋째 줄에 로봇을 정지시키는 키의 번호 $K$가 주어진다. (0ドル \leq K \leq 7$)

출력

로봇을 정지시키는 키가 점 $P_t$ $(0 \leq t \leq 7)$ 위에 존재할 때, $t$의 값을 출력한다.

제한

서브태스크

힌트