{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eArtem is a fan of Yekaterinburg Metro. He is now renovating his room. According\r\nto his design, one of the walls of the room will be covered with white\r\nwallpaper and a green straight line will stretch across the wall from left to\r\nright. This line will remind him of the only metro line in Yekaterinburg.\r\n\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eArtem has prepared \u003ci\u003en\u003c/i\u003e wallpaper strips and drawn a green line on each strip\r\nfrom its left edge to its right edge. In which order should he put these strips\r\nonto the wall so that the green lines form one segment of a straight line\r\nstretching from the left edge of the wall to its right edge?\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eFor each strip the distance from its lower edge to the left and right endpoints\r\nof the segment drawn on it is known. All the strips are of the same width and\r\ntheir height is equal to the height of the wall. The strips may be turned\r\nupside down before being pasted to the wall.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_centered_picture\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/a29be3965adc80d85f8d8d28e2dca1ac?v\u003d1714350609\" border\u003d\"0\" alt\u003d\"Problem illustration\"\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains integers \u003ci\u003eh\u003c/i\u003e and \u003ci\u003en\u003c/i\u003e (1 ≤ \u003ci\u003eh\u003c/i\u003e ≤ 100000; \r\n1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 50000), which are the height of Artem\u0027s room and the number of\r\nprepared wallpaper strips. The \u003ci\u003ei\u003c/i\u003e-th of the following \u003ci\u003en\u003c/i\u003e lines contains\r\nintegers \u003ci\u003el\u003c/i\u003e and \u003ci\u003er\u003c/i\u003e (0 ≤ \u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e ≤ \u003ci\u003eh\u003c/i\u003e), which are the distances from the lower edge of the strip to the left and right endpoints of the green segment drawn on it.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput \u003ci\u003en\u003c/i\u003e integers separated with a space. These should be numbers\r\nof the strips as they should be pasted to the wall from left to right. If a\r\nstrip should be turned upside down before pasting, then its number should be\r\npreceded with a minus. The strips are numbered from 1 to \u003ci\u003en\u003c/i\u003e as they are given\r\nin the input. If there are several possible answers, output any of them. If it\r\nis impossible to put the wallpaper as required, output “0”.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 3\r\n3 2\r\n2 1\r\n2 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-3 1 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 3\r\n3 2\r\n2 1\r\n3 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}