{"code":"givegift","name":"Phát quà","description":"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:\r\n\r\n- 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:\r\n\r\n + $(i_1,i_2,...,i_k,j_1,j_2,...,j_p)$ là một hoán vị của $(1,2,...,n)$\r\n\r\n + $k,p$ là các số không âm.\r\n\r\n + 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$\r\n\r\n**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.\r\n\r\n

Input

\r\n\r\n+ Dòng thứ nhất chứa số nguyên $n(1\\le n\\le 10^6)$\r\n\r\n+ $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$ \r\n\r\n

Output

\r\n\r\n+ 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.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 5\r\n 10 990\r\n 200 800\r\n 360 640\r\n 2 998\r\n 998 2\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n AGAAG\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n - Ta có: $S(A) = A_1+A_3+A_4 = 10+360+2 = 372$ và $S(B)=B_2+B_5 = 800+2=802$. Từ đây ta suy ra được $|S(A)-S(B)|=430<500$ thoả mãn yêu cầu bài toán","points":350.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}