BSSPC 2019 P4 - Katyusha!

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 $N$ Katyusha units will turn a square at ($x, y$) into a death-zone (DZ). You start from the bottom left corner (square ($0, 0$)) of the grid and must reach the top right corner (square ($100, 100$)) of the grid without entering any $DZ$. You may travel in any direction laterally, but may not travel diagonally. Good luck, comrade!

Input Specification

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

Output Specification

You will print a single character, $y$ to indicate that you can reach your comrades or $n$ 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