32247번 - 이상한 나라의 끈끈이주걱

왜애앵- 슈루룩.

아무것도 모른 채 평화롭게 하늘을 날던 파리는 이상한 공간에 갇혀 버렸다. 이곳에는 하늘과 땅에서 끝을 알 수 없는 엄청난 길이의 끈끈이주걱들이 자라고 있었다. 잠자리 굴에 들어가도 정신만 차리면 산다는 속담을 떠올린 파리는 저 멀리 수많은 끈끈이주걱 사이로 이곳의 출구가 있는 것을 발견했다!

파리가 이동할 수 있는 영역을 좌표평면으로 나타내면 파리의 초기 위치는 $(0,0)$이고 출구는 $(N,0)$에 위치해 있다. 파리의 현재 위치를 $(c_{x},c_{y})$라고 할 때, 파리는 각 이동마다 $-1$ 이상의 정수 $a$를 선택하여 $(c_{x}+1,c_{y}+a)$까지 직선 경로를 따라 이동한다. 파리는 다음과 같이 위아래에서 솟은 끈끈이주걱들을 피하며 $N$번의 이동 후 출구에 도달하고 싶다.

• 아래에서 솟아 올라온 끈끈이주걱 끝의 $y$좌표가 $b$라면 그곳을 지나는 파리의 $y$좌표는 $b$ 초과여야 한다.
• 위에서 솟아 내려온 끈끈이주걱 끝의 $y$좌표가 $b$라면 그곳을 지나는 파리의 $y$좌표는 $b$ 미만이어야 한다.
• 파리는 정확히 출구에 도달해야 한다. 즉, $x$좌표가 $N$일 때 $y$좌표는 $0$이어야 한다.

각 끈끈이주걱의 $x$좌표는 $0$ 초과 $N$ 미만이며, 같은 $x$좌표에서는 $2$개 이상의 끈끈이주걱이 자라지 않는다.

끈끈이주걱에 닿으면 불쌍한 파리는 생을 마감하게 된다⋯⋯. 파리는 무사히 이곳을 탈출할 수 있을까?

첫째 줄에 출구의 위치 $N$, 끈끈이주걱의 개수 $M$이 공백을 사이에 두고 주어진다. ($0\leq M<N\leq 200\, 000$)

둘째 줄부터 $M$개의 줄에 걸쳐 끈끈이주걱의 정보 $c_{i}$, $x_{i}$, $h_{i}$가 공백으로 구분되어 주어진다. $c_{i}$가 0이면 아래에서 올라온 끈끈이주걱, 1이면 위에서 내려온 끈끈이주걱을 의미한다. $x_{i}$는 끈끈이주걱의 $x$좌표, $h_{i}$는 끈끈이주걱 끝의 $y$좌표를 의미한다. ($c_{i}\in\left\{ 0,1 \right\}$; $0<x_{i}<N$; $-1\, 000\, 000\leq h_{i}\leq 1\, 000\, 000$)

입력으로 주어지는 모든 수는 정수이며, 주어지는 $x_{i}$는 모두 다르다.

파리가 무사히 탈출할 수 있다면 stay를, 그렇지 않다면 adios를 출력한다.

끈끈이주걱의 두께는 무시한다. 즉, 어떤 끈끈이주걱이 위치한 곳을 벗어나면 더 이상 해당 끈끈이주걱과 닿을 염려가 없다.