Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3831
Permutation

Time Limit: 4 Seconds      Memory Limit: 131072 KB      Special Judge

Given two sequences {A(1), A(2), ..., A(N)} and {B(1), B(2), ..., B(N)}.

You task is to find a sequence {σ(1), σ(2), ..., σ(N)} satisfy the following conditions:

  1. {σ(1), σ(2), ..., σ(N)} is a permutation of sequence {1, 2, ..., N}
  2. ∀ 1 ≤ iN, A(σ(i)) = σ(B(i))

Input

There are multiple test cases. Each case begin with a line contains an integer N (1 ≤ N ≤ 50000). The second line contains N integers, A(1), A(2), ..., A(N) (1 ≤ A(i) ≤ N). The third line contains N integers, B(1), B(2), ..., B(N) (1 ≤ B(i) ≤ N).

Output

For each test case, if you cannot find the sequence, you should just output "IMPOSSIBLE" (without quotes). If you find the sequence, you should output two lines. In the first line, you should just output "FOUND num" (without quotes), where num is the number of sequences you find. The number may be very large, so the answer should modulo 109 + 7. And in the second line, you should output N integers σ(1), σ(2), ..., σ(N), separated by a space. If there are multiple sequences meeting the conditions, you can output any one of them.

Sample Input

4
2 3 1 3
3 3 4 1
4
2 3 1 3
1 1 2 3
12
2 1 2 2 1 1 8 7 8 8 7 7
2 1 2 2 1 1 8 7 8 8 7 7

Sample Output

FOUND 1
2 4 3 1
IMPOSSIBLE
FOUND 128
1 2 3 4 5 6 7 8 9 10 11 12

Author: LIN, Xi
Source: ZOJ Monthly, November 2014
Submit    Status