Với tinh thần "Lá lành đùm là rách", An và Giang quyết định về miền tây sông nước An Giang để phát quà cho những em gặp khó khăn. Biết rằng An có \(n\) phần quà có giá trị lần lượt là \(A_1,A_2,...,A_n\) và Giang cũng có \(n\) phần quà có giá trị lần lượt là \(G_1,G_2,...,G_n\) và những phần quà này thoả mãn một tính chất đó là: \(A_i+G_i=1000\) với \(i=\overline{1,n}\). Sau một hồi bàn bạc và suy nghĩ, An và Giang đã quyết định chia quà cho những em nhỏ theo quy tắc sau:

• Gọi \(A_{i_1},A_{i_2},...,A_{i_k}\) lần lượt là những món quà mà An phát cho những em nhỏ và \(G_{j_1},G_{j_2},...,G_{j_p}\) lần lượt là những món quà mà Giang phát cho những em nhỏ, khi đó chúng phải thoả mãn những tính chất sau:

• \((i_1,i_2,...,i_k,j_1,j_2,...,j_p)\) là một hoán vị của \((1,2,...,n)\)

• \(k,p\) là các số không âm.

• Gọi \(S(A) = A_{i_1}+A_{i_2}+...+A_{i_k}\) và \(S(B)=B_{j_1}+B_{j_2}+...+B_{j_p}\) thì \(|S(A)-S(B)|\le 500\)

Yêu cầu: In ra một chuỗi gồm \(n\) phần tử thể hiện cách phát quà của An và Giang thoả mãn yêu cầu trên, với \(A\) thể hiện là món quà An phát và \(G\) là món quà Giang phát.

Input

• Dòng thứ nhất chứa số nguyên \(n(1\le n\le 10^6)\)

• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A_i,G_i\) với \(1\le i\le n\)

Output

• In ra chuỗi phát quà cần tìm. Nếu có nhiều chuỗi thoả mãn , in ra một chuỗi bất kì. Ngược lại in ra -1 nếu không có chuỗi nào thoả mãn.

Example

5
10 990
200 800
360 640
2 998
998 2

AGAAG