AT_utpc2020_k.Special Chopsticks

のいみ酱和のいむ君想送给妈妈一双特别的筷子，于是和制作筷子的高桥老师一起动手制作。筷子由两根长度相等的木片组成。

现在，他们手头上有 $N$ 根蓝色木片和 $N$ 根黄色木片，分别标号为 $1$ 到 $N$。第 $i$ 根蓝色木片的长度是 $A_i$，第 $i$ 根黄色木片的长度是 $B_i$。每根蓝色木片和黄色木片的长度互不相同。

のいみ酱和のいむ君计划制作 $K$ 双筷子。于是，高桥老师为他们准备了 $K$ 种不同长度的红色木片，每种长度各两根。第 $i$ 种红色木片的长度是 $C_i$，而这些长度都互不相同。

两人和高桥老师将通过以下步骤重复进行 $K$ 次，以制作 $K$ 双筷子。第 $i$ 次的具体操作如下：

1. のいみ酱从现有的红色木片中选择长度为 $C_{L_i}$ 和 $C_{R_i}$ 的木片，并将这两根木片连接起来，长度为 $C_{L_i} + C_{R_i}$ 的新木片交给高桥老师。
2. のいむ君选择第 $S_i$ 根蓝色木片和第 $T_i$ 根黄色木片，将它们连接形成长度为 $A_{S_i} + B_{T_i}$ 的木片并交给高桥老师。
3. 如果这两根木片的长度差是 $M$ 的倍数，那么高桥老师可以通过添加足够长度的木片来使其长度相等，从而完成一双筷子的制作。否则，这次制作将失败。

现在，のいみ酱已经为每个步骤的 $L_i$ 和 $R_i$ 做出了选择。你的任务是判断，高桥老师和のいむ君能否恰当地选择出 $C_i, S_i, T_i$，以顺利制作出 $K$ 双筷子。如果可以，请输出一种可能的选择方案。

输入由标准输入提供，包括如下内容：

$N$ $M$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$ $L_1$ $R_1$ $\vdots$ $L_K$ $R_K$

如果无法完成要求，输出 -1。若能完成任务，则输出 $K+1$ 行，格式如下：

$C_1$ $C_2$ $\ldots$ $C_K$ $S_1$ $T_1$ $\vdots$ $S_K$ $T_K$

其中，$S_i, T_i$ 分别表示第 $i$ 步中のいむ君选择的蓝色木片和黄色木片的编号。输出需要满足以下条件：

• $1 \le C_i \le M$，且 $C_i$ 互不相同。
• $1 \le S_i, T_i \le N$，且各 $S_i$ 互不相同，各 $T_i$ 互不相同。
• $A_{S_i} + B_{T_i} \equiv C_{L_i} + C_{R_i} \pmod{M}$

在满足条件的情况下，如果有多种选择方案，输出任意一种均可。

• 输入的所有数据都是整数。
• $N = 2 \times 10^5$
• $M = 10^6 + 3$（为素数）
• $K = 4 \times 10^4$
• $1 \le A_i, B_i \le M$，且每个 $A_i$ 和 $B_i$ 各不相同。
• $1 \le L_i, R_i \le K$
• 每个 $x (1 \le x \le K)$ 在 $L_i, R_i$ 中恰好出现两次。

本翻译由 AI 自动生成