Ben is playing Mario Kart World on his brand new Nintendo Switch 2! In a moment of excitement, Ben accidentally dropped his Joy-Con, and now both the joystick and the gyroscope are broken. This means his character can only move forward in a straight line from now on. Ben wants to know if it's still possible to complete certain tracks with this limited control scheme.
You are given a map of a race track, which is represented as a rectangular grid with $$$R$$$ rows and $$$C$$$ columns. Let's define $$$(X, Y)$$$ as the cell located at the $$$X$$$-th row and the $$$Y$$$-th column. Ben starts at the cell $$$(1, 1)$$$ and is initially facing east, meaning that he travels towards increasing column indices. The finishing line is located at cell $$$(R, C)$$$. Due to his broken controller, Ben can only perform the following move: advance a cell forward in the direction he is currently facing.
The grid contains $$$K$$$ pairs of linked portals. When Ben drives onto one portal of a pair, he is instantly transported to the location of the other portal in that same pair. After teleporting, Ben continues moving forward from his new location in the same direction he was already traveling. He does not get teleported back immediately. If Ben's path would take him off the grid, he hits a wall. His kart stops permanently at his last valid cell, and his run is over. He has failed to reach the finish line.
Figure 1 The image above shows a racing track with 3 pairs of teleporter portals. It illustrates how Ben reaches the finishing cell by moving in one direction only.
As Ben's friend, your task is to help him determine if it is possible to reach the finishing line at cell $$$(R, C)$$$.
The first line of the input contains two integers: $$$R$$$ and $$$C$$$ $$$(1 \leq R, C \leq 10^9)$$$, the number of rows and columns in the grid, respectively.
The second line contains one integer $$$K$$$ $$$(0 \leq K \leq 3 \times 10^4)$$$, indicating the number of teleporter portal pairs.
The next $$$2K$$$ lines each describe one portal cell. Each line contains three integers: $$$P_r, P_c, P_{id}$$$ $$$(1 \leq P_r \leq R, 1 \leq P_c \leq C, 1 \leq P_{id} \leq K)$$$, indicating the location of the portal and the pair it belongs to. The portal is located at $$$(P_r, P_c)$$$ and belongs to the $$$P_{id}$$$-th pair. It is guaranteed that each $$$P_{id}$$$ will exist exactly twice.
Note that the $$$2K$$$ portal cells are given in the order where they are first sorted increasingly by row indices, then increasingly by column indices.
Please also note that no two teleporter portals share the same cell and there won't be any portals in the starting cell or in the finishing cell.
Print a single line containing YES if it is possible for Ben to reach the finish line, and NO otherwise.
You can output the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will be recognized as positive responses.
4 331 3 12 1 23 2 13 3 34 1 24 2 3
YES
2 512 1 12 3 1
NO
Please refer to Figure 1 for Sample 1.
In Sample 2, it is impossible for Ben to reach the finishing cell.
