난수 생성기

어린 H는 최근 무작위 알고리즘을 공부하고 있다. 무작위 알고리즘은 무작위성을 얻기 위해 난수 생성 함수(예를 들어 Pascal의 random, C/C++의 rand)를 사용하는 경우가 많다. 실제로 난수 함수는 진정한 의미에서 "무작위"가 아니고, 특정한 알고리즘에 따라 동작한다.

그러한 방법 중 하나로 다음과 같은 이차 재귀 다항식이 있다.

이 알고리즘은 음이 아닌 정수 x0, a, b, c, d를 시드 값으로 선택하고, 다음 재귀 계산으로 난수를 생성한다.

모든 i ≥ 1에 대해 $x\_i = (a \times x\_{i-1}^2 + b \times x\_{i-1} + c) \mod d$

이렇게 하면 임의 길이의 음이 아닌 정수 수열 xi를 얻을 수 있다. 일반적으로 이 수열은 무작위라고 볼 수 있다. 수열 xi를 이용해 다음 알고리즘으로 1부터 K까지 수의 무작위 순열 Ti를 만들 수 있다.

1. T를 1부터 K까지의 정수 수열로 초기화한다.
2. 수열 T에 K번의 교환을 수행한다. i번째 교환은 Ti의 값과 T(xi mod i) + 1의 값을 교환한다.

이 기본 K번의 교환 외에, 어린 H는 추가로 Q번의 교환을 수행했다. i번째 추가 교환에서 어린 H는 두 위치 ui와 vi를 골라 Tui와 Tvi의 값을 교환한다.

무작위 순열 생성기의 효율을 확인하기 위해 어린 H는 다음과 같은 문제를 만들었다.

어린 H에게는 N행 M열 격자가 있다. 어린 H는 먼저 위 과정을 따라 N×M + Q번의 교환 후 1부터 N×M까지 정수의 무작위 순열 Ti를 만든다. 그런 다음 이 N×M개의 값을 행별로, 열별로 격자에 다시 채운다. 즉, 원래 격자의 i행 j열 칸은 이제 T(i−1)·M+j의 값을 가진다.

그 다음 어린 H는 격자의 왼쪽 위 모서리(즉 1행 1열)에서 시작해, 격자 밖으로 나가지 않는다는 전제 아래 매 단계 오른쪽이나 아래로 이동하며 오른쪽 아래 모서리(즉 N행 M열)에 도달하려 한다.

어린 H는 지나간 모든 칸의 값을 작은 것부터 큰 것 순서로 적는다. 이렇게 하면 어떤 유효한 경로에 대해서도 길이 N + M − 1의 증가 수열을 얻을 수 있는데, 이를 경로 수열이라고 부르자. 어린 H는 얻을 수 있는 사전 순으로 가장 작은 경로 수열을 알고 싶어 한다.

입력의 첫째 줄에는 어린 H의 난수 생성기의 시드 값인 다섯 개의 정수 x0, a, b, c, d가 주어진다.

입력의 둘째 줄에는 세 개의 정수 N, M, Q가 주어지는데, 이는 어린 H가 1부터 N×M까지의 순열을 생성해 N×M 격자를 채운다는 뜻이다. 또한 어린 H는 N × M번의 교환을 수행한 뒤 추가로 Q번의 교환을 수행한다.

마지막 Q개 줄에는 각각 두 개의 정수 ui와 vi가 주어지는데, 이는 i번째 추가 교환이 Tui와 Tvi를 교환한다는 뜻이다.

어린 H가 얻을 수 있는 사전 순으로 가장 작은 경로 수열을 나타내는 N + M − 1개의 양의 정수를 공백으로 구분해 한 줄에 출력한다.

• 2 ≤ N, M ≤ 5000
• 0 ≤ Q ≤ 50000
• 0 ≤ a ≤ 300
• 0 ≤ b, c ≤ 108
• 0 ≤ x0 < d ≤ 108
• 1 ≤ ui, vi ≤ N × M