smoothie-web Problems Contests Ranking About
Login Register

BSSPC 2019 P4 - Katyusha!

data_usage Points
1
timer Time Limit
linear_scale Memory Limit
Created
1586405195034

Problem Statement

It is the year 1945. You are a Soviet Super-Soldier and can predict the future. You have just completed a mission to sabotage the dying capital of the Third Reich. You need to safely return to your comrades advancing on the outskirts of Berlin.

However, there are several Katyusha units that are currently firing on the area between you and your comrades. There are three types of Katyushas: the light BM-8, with an impact radius of 8 meters, the intermediate BM-13, with an impact radius of 13 meters, and the massive BM-30, with an impact radius of a whopping 30 meters. Comrade Super-Soldier, you need to determine whether you can return to your comrades and complete the final assault in the Great Patriotic War!

There will be a grid of 101 by 101 squares. Each of the NN Katyusha units will turn a square at (x,yx, y) into a death-zone (DZ). You start from the bottom left corner (square (0,00, 0)) of the grid and must reach the top right corner (square (100,100100, 100)) of the grid without entering any DZDZ. You may travel in any direction laterally, but may not travel diagonally. Good luck, comrade!

Input Specification

The first line will contain one integer, 0N50000 \le N \le 5000. Each of the next NN lines will contain 2 space-separated integers, 0xi1000 \le x_i \le 100 and 0yi1000 \le y_i \le 100.

Output Specification

You will print a single character, yy to indicate that you can reach your comrades or nn to indicate that you will die for the motherland.

Sample Input 1

2
0 1
1 0

Sample Output 1

n

Sample Input 2

21
0 1
1 1
2 1
4 0
4 1
4 2
4 3
3 3
2 3
1 3
0 7
1 7
2 7
3 7
4 7
5 7
6 7
6 6
6 5
6 4
6 3

Sample Output 2

y