시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB425515.625%

문제

공 여러개가 좌표평면 위에 있다. 공은 4가지 방향(위, 아래, 왼쪽, 오른쪽)으로만 움직이며, 폭발할 수 있다. 모든 공은 1초에 1만큼 움직인다. 공의 움직임은 연속적이다. 따라서, 1/3초동안 공은 1/3만큼 움직인다.

두 개 또는 그 이상의 공이 부딪히면, 공은 폭발하게 되고, 사라지게 된다.

공의 시작점과 이동 방향이 주어졌을 때, 절대 폭발하지 않는 공의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공의 개수 N이 주어진다.(2 ≤ N ≤ 500)

둘째 줄부터 N개의 줄에는 공의 시작 좌표와 움직이는 방향이 주어진다. 시작 좌표는 0보다 크거나 같고, 100,000,000보다 작거나 같은 자연수이고, 방향은 up, down, left, right 중 하나이다.

두 공의 시작 좌표가 같은 경우는 없다.

출력

절대로 폭발하지 않는 공의 번호를 작은 번호부터 순서대로 한 줄에 하나씩 출력한다. 첫 번째 공은 1, 두 번째 공은 2, 나머지 공도 이런식이다. 만약, 모든 공이 폭발한다면, "all"을 출력한다.

예제 입력 1

4
5 5 down
5 6 left
5 7 right
5 8 up

예제 출력 1

1
2
3
4

예제 입력 2

5
3 3 down
1 1 right
5 1 left
100000 500000 right
900000 500000 left

예제 출력 2

all

예제 입력 3

3
10 0 up
0 10 right
15 5 left

예제 출력 3

2
W3sicHJvYmxlbV9pZCI6IjMxNDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZWRcdWJjMWNcdWQ1NThcdWIyOTQgXHVhY2Y1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjZjUgXHVjNWVjXHViN2VjXHVhYzFjXHVhYzAwIFx1Yzg4Y1x1ZDQ1Y1x1ZDNjOVx1YmE3NCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWFjZjVcdWM3NDAgNFx1YWMwMFx1YzljMCBcdWJjMjlcdWQ1YTUoXHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzY3Y1x1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkKVx1YzczY1x1Yjg1Y1x1YjljYyBcdWM2YzBcdWM5YzFcdWM3NzRcdWJhNzAsIFx1ZDNlZFx1YmMxY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVhY2Y1XHVjNzQwIDFcdWNkMDhcdWM1ZDAgMVx1YjljY1x1ZDA3YyBcdWM2YzBcdWM5YzFcdWM3NzhcdWIyZTQuIFx1YWNmNVx1Yzc1OCBcdWM2YzBcdWM5YzFcdWM3ODRcdWM3NDAgXHVjNWYwXHVjMThkXHVjODAxXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIDFcLzNcdWNkMDhcdWIzZDlcdWM1NDggXHVhY2Y1XHVjNzQwIDFcLzNcdWI5Y2NcdWQwN2MgXHVjNmMwXHVjOWMxXHVjNzc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVhYzFjIFx1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWNmNVx1Yzc3NCBcdWJkODBcdWI1MmFcdWQ3ODhcdWJhNzQsIFx1YWNmNVx1Yzc0MCBcdWQzZWRcdWJjMWNcdWQ1NThcdWFjOGMgXHViNDE4XHVhY2UwLCBcdWMwYWNcdWI3N2NcdWM5YzBcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZjVcdWM3NTggXHVjMmRjXHVjNzkxXHVjODEwXHVhY2ZjIFx1Yzc3NFx1YjNkOSBcdWJjMjlcdWQ1YTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjODA4XHViMzAwIFx1ZDNlZFx1YmMxY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2Y1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2Y1XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4oMiAmbGU7IE4gJmxlOyA1MDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM4OGNcdWQ0NWNcdWM2NDAgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1YmMyOVx1ZDVhNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzJkY1x1Yzc5MSBcdWM4OGNcdWQ0NWNcdWIyOTQgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMDAsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YWNlMCwgXHViYzI5XHVkNWE1XHVjNzQwIHVwLCBkb3duLCBsZWZ0LCByaWdodCBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVhY2Y1XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjODA4XHViMzAwXHViODVjIFx1ZDNlZFx1YmMxY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2Y1XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM3OTFcdWM3NDAgXHViYzg4XHVkNjM4XHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhY2Y1XHVjNzQwIDEsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVhY2Y1XHVjNzQwIDIsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWFjZjVcdWIzYzQgXHVjNzc0XHViN2YwXHVjMmRkXHVjNzc0XHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YmFhOFx1YjRlMCBcdWFjZjVcdWM3NzQgXHVkM2VkXHViYzFjXHVkNTVjXHViMmU0XHViYTc0LCAmcXVvdDthbGwmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMxNDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLT0xJQ0EiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbnVtYmVyIG9mIHNob3BwaW5nIGNhcnRzIGZpbGxlZCB3aXRoIGV4cGxvc2l2ZXMgYXJlIGZsb2F0aW5nIGluIGEgY29vcmRpbmF0ZSBzeXN0ZW0sIGluIG9uZSBvZiB0aGUgZm91ciBtYWluIGRpcmVjdGlvbnMgKHVwLCBkb3duLCBsZWZ0IG9yIHJpZ2h0KS4gQWxsIGNhcnRzIGFyZSBtb3ZpbmcgYXQgYSBzcGVlZCBvZiBvbmUgdW5pdCBwZXIgc2Vjb25kLiBNb3ZlbWVudCBpcyBjb250aW51b3VzOyBmb3IgZXhhbXBsZSwgaW4gb25lIHRoaXJkIG9mIGEgc2Vjb25kLCBhIGNhcnQgdHJhdmVscyBvbmUgdGhpcmQgb2YgYSB1bml0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5XaGVuIHR3byBvciBtb3JlIGNhcnRzIGNvbGxpZGUgKGFyZSBhdCB0aGUgc2FtZSBwbGFjZSBhdCB0aGUgc2FtZSB0aW1lKSwgdGhlcmUgaXMgYW4gZXhwbG9zaW9uIGFuZCBhbGwgY2FydHMgdGFraW5nIHBhcnQgaW4gdGhlIGNvbGxpc2lvbiBleHBsb2RlIGFuZCBjZWFzZSB0byBleGlzdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHRoZSBzdGFydGluZyBwb2ludHMgYW5kIGRpcmVjdGlvbnMgb2YgYWxsIGNhcnRzLCBkZXRlcm1pbmVzIHdoaWNoIGNhcnRzIG5ldmVyIGV4cGxvZGUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgNTAwKSwgdGhlIG51bWJlciBvZiBjYXJ0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIGFuZCBhIHN0cmluZy4gRWFjaCBwYWlyIG9mIGludGVnZXJzIGRlc2NyaWJlcyB0aGUgc3RhcnRpbmcgY29vcmRpbmF0ZXMgb2Ygb25lIGNhcnQgKGJldHdlZW4gMCBhbmQgMTAwIDAwMCAwMDAsIGluY2x1c2l2ZSksIGFuZCB0aGUgc3RyaW5nIGRlc2NyaWJlcyB0aGUgZGlyZWNjdGlvbiBpbiB3aGljaCB0aGUgY2FydCBpcyBtb3ZpbmcgKCZxdW90O3VwJnF1b3Q7IGZvciB1cCwgJnF1b3Q7ZG93biZxdW90OyBmb3IgZG93biwgJnF1b3Q7bGVmdCZxdW90OyBmb3IgbGVmdCwgb3IgJnF1b3Q7cmlnaHQmcXVvdDsgZm9yIHJpZ2h0KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm8gdHdvIGNhcnRzIHdpbGwgc3RhcnQgYXQgdGhlIHNhbWUgY29vcmRpbmF0ZXMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBpbmRpY2VzIG9mIGFsbCBjYXJ0cyB3aGljaCBuZXZlciBleHBsb2RlLCBzb3J0ZWQgaW4gYXNjZW5kaW5nIG9yZGVyLCBvbmUgaW5kZXggcGVyIGxpbmUuIFRoZSBmaXJzdCBjYXJ0IGluIHRoZSBpbnB1dCBpcyBsYWJlbGVkIDEsIHRoZSBzZWNvbmQgaXMgbGFiZWxlZCAyIGV0Yy4gSWYgbm8gY2FydHMgc3Vydml2ZSwgb3V0cHV0ICZxdW90O2FsbCZxdW90Oy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d