Hide

Problem K
OBD Codes

Like all modern automobiles, self-driving wagons produced by Calgary-based Yraglac Inc. feature an on-board computer which emits OBD codes. When a wagon emits an OBD code, it indicates that a certain condition has been detected. For example, a wagon might emit code P2181 when the engine is overheating.

Yraglac Inc. installs a cellular radio in all of its self-driving wagons that transmits OBD codes in real-time to its central server. This allows the company to monitor wagon health in real-time and send alerts to its customers when a problem is detected.

Detecting problems using the OBD data turns out not to be a trivial task, however. Engineers at Yraglac Inc. must often look for a specific sequence of OBD codes, with specific timing, in order to determine whether a problem is occurring. For example, they might look for the code P2181, followed by P0300 after 30-90 seconds, followed by P0401 after 600-9000 seconds. The engineers want to know if any subsequence of the OBD codes emitted by a self-driving wagon satisfy the requirements, so other OBD codes can occur in between.

Your task is to write a program for Yraglac Inc. that examines the OBD codes produced by one of its self-driving wagons and determines if a certain pattern exists in it.

Input

The input begins with integers $P$ ($2 \leq P \leq 5$) and $N$ ($P \leq N \leq 2 \cdot 10^5$). $P$ is the length of the pattern to search for, and $N$ is the number of OBD codes emitted by the self-driving wagon.

The next $P$ lines describe the OBD code sequence to search for. The $i$th line begins with an OBD code $c_ i$ (5 characters, starting with P and ending with 4 digits). Except for the last code in the sequence, the code is followed by $p_ i$ and $q_ i$ ($1 \leq p_ i \leq q_ i \leq 10^9$), the minimum and maximum time interval in seconds (inclusive) required after that OBD code. All OBD codes in the sequence will be distinct.

The next $N$ lines describe the OBD codes emitted by the self-driving wagon. The $i$th line consists of an OBD code $v_ i$ (in the same format as above) followed by $t_ i$ ($1 \leq t_ i \leq 10^9$), the timestamp in seconds when the code was emitted. All timestamps will be distinct and will be provided in ascending order.

Output

Output “Yes” if the pattern is found in the OBD codes emitted by the self-driving wagon, or “No” otherwise.

Sample Input 1 Sample Output 1
3 5
P2181 30 90
P0300 600 9000
P0401
P1485 1
P2181 5
P0300 46
P9876 1234
P0401 3849
Yes
Sample Input 2 Sample Output 2
2 2
P4928 2 2
P5948
P4928 1
P5948 3
Yes
Sample Input 3 Sample Output 3
2 2
P4928 2 2
P5948
P4928 1
P5948 2
No

Please log in to submit a solution to this problem

Log in