Chitti in Trouble
Time: 1 s
Memory: 125 MB
Memory: 125 MB
"Hello, I am Chitti, Speed 1 TeraHertz. Memory 1 Zettabyte. Help me, I am in trouble."
Chitti is stuck in a movement puzzle. Can you help him?
Chitti begins at the origin point \(\boldsymbol{(0,0)}\) on a \(\boldsymbol{2D}\) grid. The robot receives a sequence of movement commands, each represented as a string in the format "<direction><number>" — for example, "N3", "E22", etc.
Each command tells the robot to move a certain number of steps in one of the four cardinal directions:
After executing all the commands, the robot reaches a final position on the grid.
You are then given \(\boldsymbol{M}\) target points on the grid. For each target point \(\boldsymbol{(a_i,b_i)}\), determine whether the robot can reach that point from its final position using only diagonal moves.
In a diagonal move, both the X and Y coordinates must increase or decrease by exactly 1.
Chitti is stuck in a movement puzzle. Can you help him?
Chitti begins at the origin point \(\boldsymbol{(0,0)}\) on a \(\boldsymbol{2D}\) grid. The robot receives a sequence of movement commands, each represented as a string in the format "<direction><number>" — for example, "N3", "E22", etc.
Each command tells the robot to move a certain number of steps in one of the four cardinal directions:
- 'N' (North): increases \(\boldsymbol{D}\) along the \(\boldsymbol{y-axis}\)
- 'S' (South): decreases \(\boldsymbol{D}\) along the \(\boldsymbol{y-axis}\)
- 'E' (East): increases \(\boldsymbol{D}\) along the \(\boldsymbol{x-axis}\)
- 'W' (West): decreases \(\boldsymbol{D}\) along the \(\boldsymbol{x-axis}\)
After executing all the commands, the robot reaches a final position on the grid.
You are then given \(\boldsymbol{M}\) target points on the grid. For each target point \(\boldsymbol{(a_i,b_i)}\), determine whether the robot can reach that point from its final position using only diagonal moves.
In a diagonal move, both the X and Y coordinates must increase or decrease by exactly 1.
Input
The first line contains a single integer \(\boldsymbol{T}\) — the number of test cases.Each test case consists of the following:
The first line contains a single integer \(\boldsymbol{N}\) — the number of movement commands.
The next N lines each contain a string (Containing at most 20 character) in the format CD, where \(\boldsymbol{D}\) is a integer representing the number of steps, and \(\boldsymbol{C}\) is a character representing the direction ('N', 'S', 'E', or 'W').
The following line contains a single integer \(\boldsymbol{M}\) — the number of target points.
The next \(\boldsymbol{M}\) lines each contain two integers \(\boldsymbol{a_i}\) and \(\boldsymbol{b_i}\) — the coordinates of a target point.
Constraint
\(1\leq T\leq 10^3\)\(0\leq N \leq 10^5\)
\(1 \leq M \leq 10^5\)
\(1 \leq D\leq 10^{12}\)
\(-10^{12}\leq a_i, b_i \leq 10^{12}\)
The sum of \(\boldsymbol{N}\) and \(\boldsymbol{M}\) over all test cases does not exceed \(\boldsymbol{10^5}\)
Output
For each of the \(\boldsymbol{M}\) target points, output "YES" (without quotes) if Chitti can reach the point using only diagonal moves from his final position after executing all movement commands. Otherwise, output "NO".
Examples
| Input | Output |
|---|---|
|
1
3 N2 W33 S444 3 3 2 4 4 1 2 |
YES
NO YES |
Problem Info
| Problem ID | 489 |
| Time Limit | 1000 ms |
| Memory Limit | 128000 KB |
| Moderators | munnamiraz , muhimin , mahdi_talukder , Royboy01 |
Statistics
Submit
You need to Login or Registration for submit your solution