题目描述

$1$ から $N$ の番号がついた $N$ 人の人間と、同じく $1$ から $N$ の番号がついた $N$ 個の荷物があります。 人 $i$ の体重は $a_i$, 荷物 $j$ の重さは $b_j$ です。 はじめ人 $i$ は 荷物 $p_i$ を持っており、以下の操作を $0$ 回以上繰り返すことで全ての人が自分と同じ番号の荷物を持っている状態にしたいです。

• $i,j\ (i\ \neq\ j)$ を選び、人 $i$ と人 $j$ の荷物を交換する。

ただし、人は自分の体重以上の重さの荷物を持つと疲れてしまい、その後一切操作には加われません (すなわち、$i,j$として選べません)。 特に、 $a_i\ \leq\ b_{p_i}$ なら一度も操作に加われません。

条件を満たす操作列があるか判定し、存在するならばそのうち操作回数が最小であるものをひとつ構成してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $a_2$ $\ldots$ $a_N$ $b_1$ $b_2$ $\ldots$ $b_N$ $p_1$ $p_2$ $\ldots$ $p_N$

输出格式

どのように操作しても条件を満たせない場合、-1 を出力せよ。 条件を満たすことが可能な場合、以下のフォーマットで操作列を出力せよ。

$K$ $i_1$ $j_1$ $i_2$ $j_2$ $:$ $i_K$ $j_K$

ここで $K$ は操作回数であり、 $i_t,j_t$ は $t$ 回目の操作で選んだ人間の番号である。

解が複数存在する場合、どれを出力しても構わない。

题目大意

有 $N$ 个人和行李，编号从 $1$ 到 $N$。第 $i$ 个人的重量是 $a_i$，第 $j$ 个行李的重量是 $b_j$。

最初，第 $i$ 个人有行李 $p _ i$，我们希望进行以下操作，以便第 $i$ 个人将有行李 $i (1 \le i \le N)$。

选择 $i,j(1 \le i \le j \le N)$，交换第 $i$ 个人和第 $j$ 个人的行李。

当操作过程中，第 $i$ 个人的重量 $\le$ 第 $i$ 个行李的重量即 $a_i \le b_{p _ i}$ 时，这个人就不能参加任何操作。

确定是否存在实现目标的操作序列，如果是，用尽可能少的操作数量构造一个这样的序列。如果不行，输出 $-1$。

4
3 4 8 6
5 3 1 3
3 4 2 1

3
3 4
1 3
4 2

4
1 2 3 4
4 3 2 1
4 3 2 1

-1

1
58
998244353
1

0

提示

制約

• $1\ \leq\ N\ \leq\ 200000$
• $1\ \leq\ a_i,b_i\ \leq\ 10^9$
• $p$ は $1,\ \ldots\ ,N$ の順列
• 入力される数はすべて整数

Sample Explanation 1

初期状態で人 $1,2,3,4$ が持っている荷物の重さはそれぞれ $1,3,3,5$ なので、初期状態では誰も疲れていません。 まず人 $3$ と $4$ で操作をします。人 $1,2,3,4$ が持っている荷物の重さはそれぞれ $1,3,5,3$ なので、まだ誰も疲れていません。 次に人 $1$ と $3$ で操作をします。人 $1,2,3,4$ が持っている荷物の重さはそれぞれ $5,3,1,3$ なので、人 $1$ が疲れます。 最後に人 $4$ と $2$ で操作をします。人 $1,2,3,4$ が持っている荷物の重さはそれぞれ $5,3,1,3$ なので、これで新たに疲れる人はいません。 これによって全員が正しい荷物を持っている状態になり、さらにこれは最小の操作回数なので、正しい出力の一つです。

Sample Explanation 2

条件を満たすように操作することは出来ません。

Sample Explanation 3

初期状態で条件を満たしています。