403969: GYM101375 J MaratonIME goes to Mito

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. MaratonIME goes to Mitotime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

On MaratonIME's first trip to Mito, a restaurant, our dearest friend Estrela displayed some trouble to walk streets with trees. Every time he walked close enough to one, something really bad happened to him.

To avoid further harm, he decided to split the sidewalk into three separate lanes called S, M and H, each one approximately one meter wide, being S the one close to the street, M the one in the middle and H the one next to the houses. You can think of the region where Estrela walks as a grid with 3 lines (the lanes S, M and H) and n columns. Estrela is placed at the beginning (meter 1) of the sidewalk and wants to walk to meter n, where Mito is located. He knows the location of all the trees on his path and wants you to tell him if he can make it there unharmed. In order to guarantee that Estrela will arrive at Mito safely, he must not walk over any of the eight cells adjacent to the trees neither on the cells where trees are located.

The positions of the trees are given ordered, in other words, if i < j, the i-th tree wont be further away from the column 1 than the j-th tree.

Estrela can start and finish his walk at any lane.

The figure exemplifies the second test case. The dashed path is the path chosen by Estrela.

Input

In the first line there are two integers n e m the distance that Estrela wants to walk and the number of trees.

Then m lines follow, in the i-th line there is an integer ai and a character ci, meaning the i-th tree is in the lane ci and in the column ai. It is guaranteed that, if 1 ≤ i < j ≤ m, then ai ≤ aj, and no two trees in the input have the same lane and column.

Limits

  • 3 ≤ n ≤ 105.
  • 1 ≤ m ≤ 104.
  • 1 ≤ ai ≤ n e c1 = S or M or H for all i.
Output

Print "Yes" (without quotes) if Estrela can get to Mito safe and sound or "No" if not.

ExamplesInput
4 2
1 S
4 S
Output
Yes
Input
5 2
1 H
5 S
Output
Yes

加入题单

上一题 下一题 算法标签: