프로세서 디자인
시간 제한1초메모리 제한128 MB
비트 회전과 XOR 출력 명령 기록이 주어질 때, 이를 만족하는 사전순 최소의 초기 32비트 레지스터 값들을 XOR 관계 기반 유니온파인드로 복원합니다.
문제
보섭이는 컴퓨터 구조와 논리 과제로 작은 프로세서를 설계했다. 이 프로세서에는 1번부터 N번까지 번호가 붙은 N개의 레지스터가 있다. 각 레지스터는 일반적인 이진수 형태의 unsigned 32비트 정수를 저장하며, 값의 범위는 0부터 2^32 - 1까지이다. 프로세서는 다음 두 가지 명령을 수행할 수 있다.
보섭이는 프로세서를 이미 만들었지만, 레지스터에 저장된 값을 직접 읽는 명령을 만들지 않았다는 사실을 알게 되었다. 따라서 특정 레지스터의 값을 알아내려면 1번 명령과 2번 명령을 적절히 이용해야 한다. 프로세서가 명령을 수행한 순서와 2번 명령이 출력한 값들이 주어질 때, 처음에 각 레지스터에 저장되어 있던 값을 구하시오.
가능한 초기값의 배열이 여러 가지라면, 사전순으로 가장 작은 배열을 출력한다.
입력
첫째 줄에 레지스터의 수 N과 프로세서가 수행한 명령의 수 E가 주어진다. (2 <= N <= 100,000, 1 <= E <= 100,000)
이후 프로세서가 수행한 명령이 순서대로 하나씩 주어진다. 모든 명령은 올바르며 1 <= K, L <= N, 0 <= M < 32를 만족한다. 2번 명령이 주어진 경우에는 그 다음 줄에 시스템 버스가 출력한 결과가 10진수로 주어진다.
출력
첫째 줄에 N개 레지스터의 초기값을 1번 레지스터부터 차례대로 공백으로 구분하여 출력한다.
주어진 출력값들을 만들 수 있는 초기값의 배열이 없다면 -1을 출력한다.