题目背景

一场大型循环赛即将开幕。共有 $n$ 名选手，每两名选手之间都已经确定了唯一的胜负关系：对于任意两名不同的选手 $i$ 和 $j$，要么 $i$ 战胜 $j$，要么 $j$ 战胜 $i$，不会同时发生，也不会出现平局。

赛事导演希望安排一条“冠军巡游路线”：从某位选手出发，每一步都沿着“胜者指向败者”的方向走向下一位选手，恰好访问每名选手一次，最后还能从最后一名选手回到起点。

请找出任意一条满足条件的巡游路线；若不存在，则报告无解。

题目描述

给定一个包含 $n$ 个顶点的有向图 $G$，顶点编号为 $0,1,\ldots,n-1$。

对于任意两个不同的顶点 $i,j$，以下两条有向边中恰好存在一条：

• $i o j$；
• $j o i$。

这样的有向图称为锦标赛图。

一条哈密顿回路是一个长度为 $n$ 的顶点序列

$$p_0,p_1,\ldots,p_{n-1},$$

满足：

1. $p_0,p_1,\ldots,p_{n-1}$ 恰好是 $0,1,\ldots,n-1$ 的一个排列；
2. 对所有 $0\le i<n-1$，图中存在有向边 $p_i o p_{i+1}$；
3. 图中还存在有向边 $p_{n-1} o p_0$。

由于直接给出完整邻接矩阵可能很大，图的边方向由参数生成。

首先令 value = seed。按照以下伪代码生成所有边：

value := seed
for i := 0 .. n-1:
    for j := i+1 .. n-1:
        if value MOD 1000 <= 250:
            加入边 i -> j
        else:
            加入边 j -> i
        value := (a * value + b) MOD c

随后给出 $m$ 对顶点 $(d_k,e_k)$。按照输入顺序依次执行：

删除 e_k -> d_k
加入 d_k -> e_k

因此，如果同一对顶点在这些修改中出现多次，最后一次修改决定最终方向。

请输出任意一条哈密顿回路。若图中不存在哈密顿回路，输出 -1。

本题是构造题，需要使用 Special Judge。整理包按要求不包含 SPJ 程序。

输入格式

第一行包含五个整数 $n,\mathit{seed},a,b,c$。

第二行包含一个整数 $m$，表示需要强制修改方向的边数。

接下来 $m$ 行，每行包含两个整数 $d_k,e_k$，表示最终将这对顶点之间的边设为

$$d_k o e_k.$$

输出格式

若图中不存在哈密顿回路，输出一行一个整数：

-1

否则，输出一行 $n$ 个互不相同的整数

$$p_0,p_1,\ldots,p_{n-1},$$

表示一条哈密顿回路。

只要输出满足条件，任意合法答案均可接受。

数据范围

• $3\le n\le 1000$；
• $1\le \mathit{seed},a,b,c\le 10^9$；
• $1\le m\le 1000$；
• $0\le d_k,e_k<n$；
• $d_k e e_k$。

样例

样例 1

输入

3 1 1 1 1
3
0 1
0 2
1 2

输出

-1

说明

生成的锦标赛图不存在哈密顿回路。

样例 2

输入

4 1 1 1 1
6
0 3
1 0
1 2
2 0
3 1
3 2

输出

1 2 0 3

说明

该图存在哈密顿回路。回路可以从任意顶点开始输出，因此循环移位后的序列也都是合法答案。

样例 3

输入

4 1 1 1 1
8
0 1
0 3
1 2
2 0
2 3
3 1
1 0
0 1

输出

1 2 0 3

说明

同一对顶点可能被修改多次，只有最后一次修改决定最终边方向。

样例 4

输入

6 1 1 1 1
15
5 3
4 5
4 2
3 4
2 5
2 3
2 0
1 5
1 4
1 3
1 2
0 5
0 4
0 3
0 1

输出

3 4 2 0 1 5

样例 5

输入

6 987654323 999777888 979797979 987654323
1
0 1

输出

-1

样例 6

输入

8 2018 1337 10001 10007
1
0 2

输出

3 4 0 1 2 7 6 5

提示

锦标赛图存在哈密顿回路，当且仅当它是强连通图。