Xorshift+ 예측

다음과 같은 의사 난수 생성기를 생각해 보자.

  function xorshift()
    last_value = internal_value
    for i = 1 to M do
      if S[i] < 0 then
        internal_value = internal_value ^ (internal_value >> -S[i])
      else
        internal_value = internal_value ^ (internal_value << S[i])
    return last_value + internal_value

여기서

• last_value는 $N$비트 지역 변수이다.
• internal_value는 $N$비트 전역 변수이며, 초깃값은 알려져 있지 않다.
• S는 값을 알고 있는 $M$개 원소의 전역 상수 배열이다.
• ^는 비트 단위 배타적 논리합(XOR)이다. 결과의 각 비트는 두 피연산자의 대응하는 비트가 같으면 $0$, 다르면 $1$이다. 예를 들어 $10 \mathbin{`^`} 12 = 6$이다. 10의 이진수는 1010, 12의 이진수는 1100이므로 결과는 0110, 곧 6의 이진수이다.
• <<와 >>는 비트 단위 왼쪽 시프트와 오른쪽 시프트이다. $N$비트 수를 $s$비트만큼 왼쪽으로 시프트하면 가장 왼쪽의 $s$개 비트가 지워지고 오른쪽에 $s$개의 $0$ 비트가 붙는다. 예를 들어 4비트 변수에서 $6 \mathbin{`<<`} 2 = 8$이다. 6의 이진수 0110에서 왼쪽 두 비트를 지우면 10이고, 오른쪽에 $0$ 비트 두 개를 붙이면 1000, 곧 8의 이진수이다. 오른쪽 시프트는 오른쪽에서 비트를 지우고 왼쪽에 비트를 붙인다.
• +는 덧셈이며, 결과에서는 가장 오른쪽 $N$비트만 사용한다.
• internal_value의 초깃값은 $0$이 아니며, S의 값은 xorshift를 무한히 호출하면 internal_value가 $1 \ldots 2^N-1$의 모든 값을 가지도록 정해져 있다.

위의 xorshift 함수를 $K$번 연속으로 호출하여 얻은 반환값 $K$개를 입력받아, 그다음 호출에서 반환될 값을 구하는 프로그램을 작성하시오.

입력 파일의 첫 줄에 세 정수 $N$ ($2 \le N \le 64$), $M$ ($2 \le M \le 10$), $K$ ($100 \le K \le 200\,000$)가 주어진다. 둘째 줄에는 $M$개의 정수 $S_i$ ($1-N \le S_i \le N-1$)가 주어진다. 셋째 줄에는 xorshift 함수를 $K$번 연속으로 호출했을 때의 반환값인 $K$개의 정수 $V_j$ ($1 \le V_j < 2^N$)가 주어진다.

출력 파일의 한 줄에 xorshift 함수의 다음 호출에서 반환되는 값을 정수 하나로 출력한다.