27506번 - 함수열과 쿼리

함수열이란 함수들의 열로 $\{f_i\}_{i\in\mathbb{N}}$의 형태로 정의되며, 나열하면 $f_1, f_2, f_3,...$ 과 같이 표현됩니다.

함수의 합성 "$\circ$"는 $(f\circ g)(x) = f(g(x))$의 식으로 정의됩니다. 이것도 마찬가지로 여러 개로 이어지면, $$(f_1\circ f_2 \circ f_3)(x) = (f_1 \circ f_2)(f_3(x)) = f_1(f_2(f_3(x))$$ 이렇게 표현됩니다.

예를 들어 $f_1(3) = 2, f_2(1) = 3, f_3(2) = 1$ 이라면 $$(f_1\circ f_2 \circ f_3)(2) = f_1(f_2(f_3(2)) = f_1(f_2(1)) = f_1(3) = 2$$와 같이 계산할 수 있습니다.

문제에서는 다음 조건을 만족하는 함수 $n$개가 차례대로 주어집니다.

• $1 \le x \le 5$ 를 만족하는 자연수 $x$에 대해 $f(x)$는 자연수이고, $1 \le f(x) \le 5$ 입니다.
• $x \ne y$ 이면 $f(x) \ne f(y)$ 입니다.

즉, $1$ 부터 $5$ 까지로 이루어진 순열이 $n$개 주어집니다.

이어서 다음과 같은 쿼리가 주어집니다.

• $u$ $a$ $b$ $y_1$ $y_2$ $y_3$ $y_4$ $y_5$

각 쿼리에서 $a$와 $b$는 $a \le u \le b$를 만족하게 주어지며, $g = (f_a\circ f_{a+1}\circ f_{a+2}\circ ... \circ f_{b})$인 $g$가 $1 \le i \le 5$ 인 $i$에 대해 $g(i) = y_i$가 되도록 $f_u$를 변경했음을 의미합니다.

각각의 쿼리마다 $f_u$가 어떤 함수로 변했는지 구합니다.

단, 쿼리에 의해 변한 $f_u$는 그대로 유지됩니다. 즉, 쿼리가 누적됩니다.

첫 번째 줄에 함수열의 길이 $n(3\le n \le 100\,000)$이 주어집니다. 두 번째 줄부터 $n+1$번째 줄까지 함수열이 주어집니다. 각 $i + 1$번째 줄에는 $f_i$가 주어지며, $f_i(1)$, $f_i(2)$, $f_i(3)$, $f_i(4)$, $f_i(5)$가 차례대로 공백으로 구분되어 주어집니다.

$n+2$번째 줄에 쿼리의 수 $q(1\le q \le 100\,000)$가 주어집니다. 이후 $n + 3$번째 줄 부터 $n + q + 2$번째 줄까지 문제에서 제시된 쿼리가 주어집니다.

각 쿼리는 줄마다

$u$ $a$ $b$ $y_1$ $y_2$ $y_3$ $y_4$ $y_5$

의 형태로 주어지며 $1 \le a\le u \le b \le n$이고 $i \ne j$ 이면 $y_i \ne y_j$임을 만족하게 주어집니다.

각 쿼리마다 $f_u(1)$, $f_u(2)$, $f_u(3)$, $f_u(4)$, $f_u(5)$가 어떤 값으로 변했는지 차례대로 공백으로 구분하여 출력합니다. 경우에 따라서는 $f_u$가 변하지 않았을 때에 쿼리를 만족할 수 있습니다. 만약 $f_u$가 변경되지 않았어도 같은 형식으로 출력합니다.