Description

Since we are now undergoing the covid-19 pandemic, the CECC(疫情指揮中心) announce that two people should keep space between themselves at a social distance at s meters.

Inside a classroom, there are n seats numbered from 1 to n in a row and there are walls on the left of the 1-st seat and on the right of the n-th seat. m students numbered from 1 to m are coming to class. The distance between to neighboring seats or walls is 1 meter. Initially there are no people on the seats.

Each student takes a seat and leaves the seat at some time and they will take the seat that is farthest from the wall and the other people. If there are multiple seats to choose from, he or she will choose the leftmost one (i.e. the seat with smallest number).

More detailed description of how a student pick a seat:

Let D be minimum distance between any two people (note that walls are not people) during the whole class. If D >= s then we say the class is safe, otherwise it is not safe.

Given the time when each student enters and leaves classroom. Your professor wants to know whether he is clockwise whether he follows the CECC's rules , so he wants you to write a program to calculate the value of D and tells him if the class is safe or not.

Explanation for sample IO

Let d be the minimum distance between any two people at a specific time.

0. _ _ _ _ _ _ _ _ _, d = INF

1. _ _ _ _ 1 _ _ _ _, d = INF

2. _ 2 _ _ 1 _ _ _ _, d = 3

3. _ 2 _ _ _ _ _ _ _, d = INF

4. _ 2 _ _ _ 3 _ _ _, d = 4

5. _ _ _ _ _ 3 _ _ _, d = INF

6. _ _ _ _ _ _ _ _ _, d = INF

During the whole class min d = 3, therefore D = 3 < S = 5, it is not safe.

Input

The first line are three integers n m s (mentioned in problem description).

Then there are 2 x m lines, each line represents the event that one student enters or leaves the classroom. For the k-th line:

• i x means that the student with number x comes in the classroom and takes a seat at time k

• o x means that the student with number x leaves the seat and goes out the classroom at time k

It is guaranteed that:

• A student will never comes back to class after he or she leaves

• When a student leaves, he or she must be in the classroom (i.e. for a student x, i x must appear before o x)

Technical Restrictions:

• For first test case:

  • 1 <= m <= n <= 10

  • 1 <= s <= 10

• For second test case:

  • 1 <= m <= n <= 2000

  • 1 <= s <= 2000

• For third test case:

  • 1 <= m <= 2000

  • 1 <= m <= n, s <= 10^9

• For fourth and fifth test case:

  • 1 <= m <= 10^5

  • 1 <= m <= n, s <= 10^9

Output

Please output D (If D is infinity, then print "INF").  Please output "YES" if it is safe and "NO" if it is not safe.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss