B"Tema is playing a very interesting computer game. During the next mission, Tema's character found himself on an unfamiliar planet. Unlike Earth, this planet is flat and can be represented as an n x m rectangle. Tema's character is located at the point with coordinates (0, 0) . In order to successfully complete the mission, he needs to reach the point with coordinates (n, m) alive. Let the character of the computer game be located at the coordinate (i, j) . Every second, starting from the first, Tema can: The aliens that inhabit this planet are very dangerous and hostile. Therefore, they will shoot from their railguns r times. Each shot completely penetrates one coordinate vertically or horizontally. If the character is in the line of its impact at the time of the shot (at the end of the second), he dies. Since Tema looked at the game's source code, he knows complete information about each shot -- the time, the penetrated coordinate, and the direction of the shot. What is the minimum time for the character to reach the desired point? If he is doomed to die and cannot reach the point with coordinates (n, m) , output -1 . The first line of the input contains a single integer T ( 1 <= T <= 10^4 ) -- the number of test cases. Then follow the descriptions of the test cases. The first line of each test case contains two integers n and m ( 1 <= n cdot m <= 10^4 ) -- the size of the planet, its height and width. The second line of each test case contains a single integer r ( 1 <= r <= 100 ) -- the number of shots. Then follow r lines, each describing one shot. A shot is described by three integers t , d , coord . Where t is the second at which the shot will be fired ( 1 <= t <= 10^9 ). d is the direction of the shot ( d = 1 denotes a horizontal shot, d = 2 denotes a vertical shot). coord is the size of the penetrated "...