Description

Note: This problem is almost the same as social distance, but there are no walls in this problem.

(Don't forget to keep social distance during lifesaving training ><)

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 no walls. m students numbered from 1 to m are coming to class. The distance between to neighboring seats 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 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).

Let D be minimum distance between any two 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 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. The following are the first 6 moments.

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

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

2. 1 _ _ _ _ _ _ _ 2, d = 8

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

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

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

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

During the whole class min d = 2, therefore D = 2 < 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 all test cases, m <= n

• Test 1 - 3: Small test cases, can be solved with brute force

  • Test 1: 1 <= n, m, S <= 30

  • Test 2 - 3: 1 <= n, m, S <= 2000

• Test 4 - 7: It is guaranteed that the first two students who enter the classroom are same as the last two student to leave the classroom

  • Test 4: 1 <= n, m, S <= 30

  • Test 5: 1 <= m <= 2000 and 1 <= n, S <= 10^5

  • Test 6-8: 1 <= m <= 10^5 and 1 <= n, S <= 10^9

• Test 8 - 12: Good luck and have fun

  • 1 <= m <= 10^5 and 1 <= 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