Contest Duration: - (local time) (120 minutes) Back to Home
C - Too Heavy /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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} なら一度も操作に加われません。

### 制約

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

### 入力

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_tt 回目の操作で選んだ人間の番号である。

### 入力例 1

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


### 出力例 1

3
3 4
1 3
4 2


まず人 34 で操作をします。人 1,2,3,4 が持っている荷物の重さはそれぞれ 1,3,5,3 なので、まだ誰も疲れていません。

これによって全員が正しい荷物を持っている状態になり、さらにこれは最小の操作回数なので、正しい出力の一つです。

### 入力例 2

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


### 出力例 2

-1


### 入力例 3

1
58
998244353
1


### 出力例 3

0


Score : 600 points

### Problem Statement

There are N people numbered 1 to N and N pieces of baggage numbered numbered 1 to N. Person i has a weight of a_i, and Baggage j has a weight of b_j. Initially, Person i has Baggage p_i. We want to do the operation below zero or more times so that each Person i will have Baggage i.

• Choose i,j (i \neq j), and swap the baggages of Person i and Person j.

However, when a person has a piece of baggage with a weight greater than or equal to his/her own weight, the person gets tired and becomes unable to take part in a future operation (that is, we cannot choose him/her as Person i or j). Particularly, if a_i \leq b_{p_i}, Person i cannot take part in any operation.

Determine whether there is a sequence of operations that achieves the objective, and if so, construct one such sequence with the minimum possible number of operations.

### Constraints

• 1 \leq N \leq 200000
• 1 \leq a_i,b_i \leq 10^9
• p is a permutation of 1, \ldots, N.
• All numbers in input are integers.

### Input

Input is given from Standard Input in the following format:

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


### Output

If no sequence of operations achieves the objective, print -1. Otherwise, print a sequence of operations in the following format:

K
i_1 j_1
i_2 j_2
:
i_K j_K


Here, K is the number of operations, and i_t, j_t represent the people chosen in the t-th operation.

If there are multiple solutions, any of them will be accepted.

### Sample Input 1

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


### Sample Output 1

3
3 4
1 3
4 2


Initially, People 1, 2, 3, 4 has pieces of baggage with weights 1, 3, 3, 5, respectively, so no one is tired.

First, we do the operation choosing Person 3 and 4. Now, people 1, 2, 3, 4 has pieces of baggage with weights 1, 3, 5, 3, so no one is tired yet.

Second, we do the operation choosing Person 1 and 3. Now, people 1, 2, 3, 4 has pieces of baggage with weights 5, 3, 1, 3, so Person 1 gets tired.

Lastly, we do the operation choosing Person 4 and 2. Now, people 1, 2, 3, 4 has pieces of baggage with weights 5, 3, 1, 3, so no one gets tired.

This sequence of operations has made everyone have the right piece of baggage, with the minimum possible number of operations, so it is valid.

### Sample Input 2

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


### Sample Output 2

-1


No sequence of operations achieves the objective.

### Sample Input 3

1
58
998244353
1


### Sample Output 3

0


The objective is already achieved in the initial state.