Or 머신

우리는 C++의 | 연산 하나만을 위해 극도로 최적화한 컴퓨터인 Or 머신을 개발하고 있다.

Or 머신에는 $n$개의 레지스터가 있고, 각 레지스터에는 $2^8$ 미만의 음이 아닌 정수가 들어 있다. 레지스터를 $x_1, x_2, \cdots, x_n$이라 하자. 프로그램은 $l$개의 연산 목록으로 표현된다. 각 연산은 정수 쌍 $(a, b)$로 표현되며, 이는 $x_a$를 $x_a$와 $x_b$의 비트 OR로 갱신하라는 뜻이다.

Or 머신은 프로그램, 레지스터의 초기값, 양의 정수 $t$를 받는다. 실행하면 프로그램의 각 연산을 차례대로 하나씩 수행한다. 마지막 연산을 수행하면 다시 첫 번째 연산으로 돌아가 이 과정을 반복한다. 머신은 정확히 $t$개의 연산을 수행한 뒤 멈춘다.

우리는 이 머신이 범용 컴퓨터보다 훨씬 빠르길 바라지만, 하드웨어 최적화만으로는 부족할 듯하다. 소프트웨어 최적화를 도와줄 수 있는가?

첫째 줄에 세 정수 $n$, $l$, $t$가 주어진다. ($1 \leq n, l \leq 2^{18}$, $1 \leq t \leq 10^{18}$) $l$은 프로그램의 길이이다.

다음 $l$개의 줄에 프로그램이 주어진다. 각 줄에는 해당 연산에 참여하는 레지스터 쌍을 나타내는 두 정수 $a$, $b$가 주어진다. ($1 \leq a, b \leq n$)

마지막 줄에는 레지스터의 초기값 $x_1, \cdots, x_n$이 $n$개의 정수로 주어진다. ($0 \le x_i < 2^8$)

$t$개의 연산을 수행한 뒤의 레지스터 값 $x_1, \cdots, x_n$을 한 줄에 $n$개의 정수로 출력한다.