Futon

The sales department of a company is on a retreat at a hot spring town. To get to know each other better, everyone sleeps in one large room of a ryokan, a Japanese inn.

In a ryokan people sleep on futons laid out on the floor. Everyone has already put a futon wherever they liked. All that is left is to lie down, but one thing worries them. Pointing your feet toward somebody else's head is bad manners in Japan. Whether the current layout lets everyone keep good manners is not obvious at a glance. Write a program that answers the question.

Model the situation as follows. The room is a grid on the $xy$ plane, with the $x$ axis pointing right and the $y$ axis pointing up. One futon covers two cells that share a side. Each person puts a pillow on one of those two cells and rests their head there. Their feet go on the other cell. If the cell holding one person's feet shares a side with the cell holding another person's head, the manners are bad. The direction each of the two futons is laid in does not matter. If no such pair of cells exists, everyone is fine.

Every person can freely choose which of their two cells holds the pillow. Decide whether the choices can be made so that no bad pair exists.

The input is a sequence of datasets. Each dataset has the following format.

n
x1 y1 dir1
...
xn yn dirn

$n$ is the number of futons ($1 \le n \le 20000$). $(x_i, y_i)$ is the coordinate of the bottom left cell of the $i$-th futon. $dir_i$ is either x or y. x means the futon is laid horizontally and covers $(x_i, y_i)$ and $(x_i + 1, y_i)$. y means it is laid vertically and covers $(x_i, y_i)$ and $(x_i, y_i + 1)$. Every coordinate value is a non-negative integer not greater than $10^9$.

No two futons in the input overlap.

The input ends with a line holding a single $0$. That line is not a dataset, so do not process it.

For each dataset, print Yes on its own line if the bad pairs can be avoided, or No if they cannot.