Cryptography

시간 제한1초메모리 제한1024 MB

요약
크기가 2^m인 배열 f, g, h로 정의되는 암호화 함수의 출력 쌍이 주어질 때, 각 출력에 대응하는 유일한 (x, y)를 복원한다.
난이도

어려움10점 중 8점

유형
해시맵, 비트 연산, 구현
정답자
아직 제출이 없습니다

문제

Given three arrays ff, gg, hh of length 2m2^m, Bobo defines a cryptographic function enc(x,y)=(a,b)\mathrm{enc}(x, y) = (a, b) where

  • a=y⊕g\[x⊕f\[y]]a = y \oplus g\[x \oplus f\[y]],
  • b=x⊕f\[y]⊕h\[y⊕g\[x⊕f\[y]]]b = x \oplus f\[y] \oplus h\[y \oplus g\[x \oplus f\[y]]].

He also has qq questions (a_1,b_1),…,(a_q,b_q)(a\_1, b\_1), \dots, (a\_q, b\_q).

For each (a_i,b_i)(a\_i, b\_i), find a pair of integers (x,y)(x, y) where 0≤x,y<2m0 \leq x, y < 2^m and enc(x,y)=(a_i,b_i)\mathrm{enc}(x, y) = (a\_i, b\_i). It is guaranteed that for each (a_i,b_i)(a\_i, b\_i), there exists a unique pair (x,y)(x, y) satisfying the condition.

Note: ⊕\oplus denotes the bitwise exclusive-or, i.e., xor.

입력

The input consists of several test cases terminated by end-of-file. For each test case,

The first line contains two integers mm and qq.

The second line contains 2m2^m integers f\[0],…,f\[2m−1]f\[0], \dots, f\[2^m - 1].

The third line contains 2m2^m integers g\[0],…,g\[2m−1]g\[0], \dots, g\[2^m - 1].

The forth line contains 2m2^m integers h\[0],…,h\[2m−1]h\[0], \dots, h\[2^m - 1].

For the following qq lines, the ii-th line contains two integers a_ia\_i and b_ib\_i.

출력

For each question, output two integers which denote the found xx and yy.

제한

  • 1≤m≤161 \le m \leq 16
  • 1≤q≤1051 \leq q \leq 10^5
  • 0≤f\[i],g\[i],h\[i]<2m0 \leq f\[i], g\[i], h\[i] < 2^m for each 0≤i<2m0 \leq i < 2^m
  • 0≤a_i,b_i<2m0 \leq a\_i, b\_i < 2^m for each 1≤i≤q1 \leq i \leq q
  • In each input, the sum of 2m2^m does not exceed 10510^5. The sum of qq does not exceed 10510^5.

예제1

  1. 예제 1

    입력
    2 2
0 1 2 3
1 2 3 0
2 3 0 1
0 1
2 3
1 1
0 0
0 0
0 0
0 0
    예상 출력
    3 0
1 2
0 0