시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 3 3 100.000%

문제

공 여러개가 좌표평면 위에 있다. 공은 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
W3sicHJvYmxlbV9pZCI6IjMxNDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZWRcdWJjMWNcdWQ1NThcdWIyOTQgXHVhY2Y1IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWFjZjUgXHVjNWVjXHViN2VjXHVhYzFjXHVhYzAwIFx1Yzg4Y1x1ZDQ1Y1x1ZDNjOVx1YmE3NCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWFjZjVcdWM3NDAgNFx1YWMwMFx1YzljMCBcdWJjMjlcdWQ1YTUoXHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzY3Y1x1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkKVx1YzczY1x1Yjg1Y1x1YjljYyBcdWM2YzBcdWM5YzFcdWM3NzRcdWJhNzAsIFx1ZDNlZFx1YmMxY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVhY2Y1XHVjNzQwIDFcdWNkMDhcdWM1ZDAgMVx1YjljY1x1ZDA3YyBcdWM2YzBcdWM5YzFcdWM3NzhcdWIyZTQuIFx1YWNmNVx1Yzc1OCBcdWM2YzBcdWM5YzFcdWM3ODRcdWM3NDAgXHVjNWYwXHVjMThkXHVjODAxXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIDFcLzNcdWNkMDhcdWIzZDlcdWM1NDggXHVhY2Y1XHVjNzQwIDFcLzNcdWI5Y2NcdWQwN2MgXHVjNmMwXHVjOWMxXHVjNzc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHVhYzFjIFx1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWNmNVx1Yzc3NCBcdWJkODBcdWI1MmFcdWQ3ODhcdWJhNzQsIFx1YWNmNVx1Yzc0MCBcdWQzZWRcdWJjMWNcdWQ1NThcdWFjOGMgXHViNDE4XHVhY2UwLCBcdWMwYWNcdWI3N2NcdWM5YzBcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjZjVcdWM3NTggXHVjMmRjXHVjNzkxXHVjODEwXHVhY2ZjIFx1Yzc3NFx1YjNkOSBcdWJjMjlcdWQ1YTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjODA4XHViMzAwIFx1ZDNlZFx1YmMxY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2Y1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM3YWMgXHVjOTA0XHVjNWQwIFx1YWNmNVx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuKDIgJmxlOyBOICZsZTsgNTAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNmNVx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjODhjXHVkNDVjXHVjNjQwIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyZGNcdWM3OTEgXHVjODhjXHVkNDVjXHViMjk0IDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAwLDAwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWFjZTAsIFx1YmMyOVx1ZDVhNVx1Yzc0MCB1cCwgZG93biwgbGVmdCwgcmlnaHQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNDUwIFx1YWNmNVx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjODhjXHVkNDVjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YzgwOFx1YjMwMFx1Yjg1YyBcdWQzZWRcdWJjMWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNmNVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjNzkxXHVjNzQwIFx1YmM4OFx1ZDYzOFx1YmQ4MFx1ZDEzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YWNmNVx1Yzc0MCAxLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YWNmNVx1Yzc0MCAyLCBcdWIwOThcdWJhMzhcdWM5YzAgXHVhY2Y1XHViM2M0IFx1Yzc3NFx1YjdmMFx1YzJkZFx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWJhYThcdWI0ZTAgXHVhY2Y1XHVjNzc0IFx1ZDNlZFx1YmMxY1x1ZDU1Y1x1YjJlNFx1YmE3NCwgJnF1b3Q7YWxsJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS09MSUNBIiwiZGVzY3JpcHRpb24iOiI8cD5BIG51bWJlciBvZiBzaG9wcGluZyBjYXJ0cyBmaWxsZWQgd2l0aCBleHBsb3NpdmVzIGFyZSBmbG9hdGluZyBpbiBhIGNvb3JkaW5hdGUgc3lzdGVtLCBpbiBvbmUgb2YgdGhlIGZvdXIgbWFpbiBkaXJlY3Rpb25zICh1cCwgZG93biwgbGVmdCBvciByaWdodCkuIEFsbCBjYXJ0cyBhcmUgbW92aW5nIGF0IGEgc3BlZWQgb2Ygb25lIHVuaXQgcGVyIHNlY29uZC4gTW92ZW1lbnQgaXMgY29udGludW91czsgZm9yIGV4YW1wbGUsIGluIG9uZSB0aGlyZCBvZiBhIHNlY29uZCwgYSBjYXJ0IHRyYXZlbHMgb25lIHRoaXJkIG9mIGEgdW5pdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2hlbiB0d28gb3IgbW9yZSBjYXJ0cyBjb2xsaWRlIChhcmUgYXQgdGhlIHNhbWUgcGxhY2UgYXQgdGhlIHNhbWUgdGltZSksIHRoZXJlIGlzIGFuIGV4cGxvc2lvbiBhbmQgYWxsIGNhcnRzIHRha2luZyBwYXJ0IGluIHRoZSBjb2xsaXNpb24gZXhwbG9kZSBhbmQgY2Vhc2UgdG8gZXhpc3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgc3RhcnRpbmcgcG9pbnRzIGFuZCBkaXJlY3Rpb25zIG9mIGFsbCBjYXJ0cywgZGV0ZXJtaW5lcyB3aGljaCBjYXJ0cyBuZXZlciBleHBsb2RlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDUwMCksIHRoZSBudW1iZXIgb2YgY2FydHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBhbmQgYSBzdHJpbmcuIEVhY2ggcGFpciBvZiBpbnRlZ2VycyBkZXNjcmliZXMgdGhlIHN0YXJ0aW5nIGNvb3JkaW5hdGVzIG9mIG9uZSBjYXJ0IChiZXR3ZWVuIDAgYW5kIDEwMCAwMDAgMDAwLCBpbmNsdXNpdmUpLCBhbmQgdGhlIHN0cmluZyBkZXNjcmliZXMgdGhlIGRpcmVjY3Rpb24gaW4gd2hpY2ggdGhlIGNhcnQgaXMgbW92aW5nICgmcXVvdDtnb3JlJnF1b3Q7IGZvciB1cCwgJnF1b3Q7ZG9samUmcXVvdDsgZm9yIGRvd24sICZxdW90O2xpamV2byZxdW90OyBmb3IgbGVmdCwgb3IgJnF1b3Q7ZGVzbm8mcXVvdDsgZm9yIHJpZ2h0KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm8gdHdvIGNhcnRzIHdpbGwgc3RhcnQgYXQgdGhlIHNhbWUgY29vcmRpbmF0ZXMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBpbmRpY2VzIG9mIGFsbCBjYXJ0cyB3aGljaCBuZXZlciBleHBsb2RlLCBzb3J0ZWQgaW4gYXNjZW5kaW5nIG9yZGVyLCBvbmUgaW5kZXggcGVyIGxpbmUuIFRoZSBmaXJzdCBjYXJ0IGluIHRoZSBpbnB1dCBpcyBsYWJlbGVkIDEsIHRoZSBzZWNvbmQgaXMgbGFiZWxlZCAyIGV0Yy4gSWYgbm8gY2FydHMgc3Vydml2ZSwgb3V0cHV0ICZxdW90O25lbWEmcXVvdDsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d