Problem: There are two rooted trees, each with N vertices. The vertices of each tree are numbered 1 through N. In the first tree, the parent of Vertex i is Vertex A_i. Here, A_i=-1 if Vertex i is the root of the first tree. In the second tree, the parent of Vertex i is Vertex B_i. Here, B_i=-1 if Vertex i is the root of the second tree.

Snuke would like to construct an integer sequence of length N, X_1 , X_2 , ... , X_N, that satisfies the following condition:

* For each vertex on each tree, let the indices of its descendants including itself be a_1 , a_2 , ..., a_k. Then, abs(X_{a_1} + X_{a_2} + ... + X_{a_k})=1 holds.



Determine whether it is possible to construct such a sequence. If the answer is possible, find one such sequence.

Constraints

* 1 \leq N \leq 10^5
* 1 \leq A_i \leq N, if Vertex i is not the root in the first tree.
* A_i = -1, if Vertex i is the root in the first tree.
* 1 \leq B_i \leq N, if Vertex i is not the root in the second tree.
* B_i = -1, if Vertex i is the root in the second tree.
* Input corresponds to valid rooted trees.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 .. A_N
B_1 B_2 .. B_N


Output

If it is not possible to construct an integer sequence that satisfies the condition, print `IMPOSSIBLE`. If it is possible, print `POSSIBLE` in the first line. Then, in the second line, print X_1 , X_2 , ... , X_N, an integer sequence that satisfies the condition.

Examples

Input

5
3 3 4 -1 4
4 4 1 -1 1


Output

POSSIBLE
1 -1 -1 3 -1


Input

6
-1 5 1 5 1 3
6 5 5 3 -1 3


Output

IMPOSSIBLE


Input

8
2 7 1 2 2 1 -1 4
4 -1 4 7 4 4 2 4


Output

POSSIBLE
1 2 -1 0 -1 1 0 -1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n, f[MAXN], dis[MAXN];
inline int getfa(int x)
{
	if(f[x] == x)
		return x;
	int root(getfa(f[x]));
	dis[x] ^= dis[f[x]];
	return f[x] = root;
}
inline void merge(int u, int v)
{
	int x = getfa(u), y = getfa(v);
	if(x == y)
		return;
	dis[y] = (dis[v] ^ dis[u] ^ 1), f[y] = x;
}
struct T
{
	int root, head[MAXN], cnt, to[MAXN], nxt[MAXN], son[MAXN];
	inline void ae(int u, int v)
	{
		++cnt, to[cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
	}
	void init()
	{
		for(int i = 1, fa; i <= n; ++i)
		{
			scanf("%d", &fa);
			if(fa == -1)
				root = i;
			else
				ae(fa, i), ++son[fa];
		}
	}
	int work(int u)
	{
		vector<int> tp;
		for(int i = head[u]; i; i = nxt[i])
			tp.push_back(work(to[i]));
		if((son[u] & 1) == 0)
			tp.push_back(u);
		sort(tp.begin(), tp.end());
		for(int i = 1; i < tp.size(); i += 2)
			merge(tp[i], tp[i + 1]);
		return tp[0];
	}
};
T A, B;
template <class T>
inline void _read(T &x)
{
	x = 0;
	char t = getchar();
	while(!isdigit(t) && t != '-') t = getchar();
	if(t == '-')
	{
		_read(x);
		x *= -1;
		return ;
	}
	while(isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
}
int main()
{
	_read(n);
	A.init(), B.init();
	for(int i = 1; i <= n; ++i)
	{
		f[i] = i, dis[i] = 0;
		if((A.son[i] & 1) != (B.son[i] & 1))
		{
			puts("IMPOSSIBLE");
			return 0;
		}
	}
	puts("POSSIBLE");
	A.work(A.root), B.work(B.root);
	for(int i = 1; i <= n; ++i)
		if((A.son[i] & 1) == 0)
			printf("%d ", (getfa(i), dis[i]) ? +1 : -1);
		else
			printf("%d ", 0);
	return 0;
}