Description

According to ancient legend, King Solomon stood for wisdom and wealth. He built a powerful and prosperous nation, amassed vast quantities of gold, ivory, and diamonds, and hid these priceless treasures in a mysterious place known as “King Solomon’s Treasure.” For centuries, people have searched for this lost treasure of ancient civilization, seeking the fabled land rich in gold and diamonds. Adventurers who pursued King Solomon’s treasure never returned, and to this day no one has solved the riddle. On a fortunate journey, Baron Henry unexpectedly obtained a treasure map of King Solomon left by a Portuguese noble three hundred years ago, written on parchment, along with a treasure-hunting manual. Tempted by the map, Baron Henry invited Colonel John and the brave elephant hunter Quatermain to begin a perilous quest for King Solomon’s treasure buried in the dark depths underground. They crossed boundless deserts and dense primeval forests, passed roaring rapids, climbed towering snowy peaks, and endured scorching heat and bitter cold. Guided by the map, they arrived at Kukuana, a mysterious and primitive land in Africa. There were cruel human sacrifices, a one-eyed tyrant Twala with a thousand wives, an old and crafty witch Gagool as ugly as a vulture, and a beautiful and intelligent lady named Foulata. In this unfamiliar and perilous land, the three treasure hunters endured countless hardships and, with Foulata’s help, finally found a vast treasure cave in the depths beneath the sea where the priceless treasure was hidden. However, under the witch Gagool’s careful plotting, disaster was quietly approaching.

The door of the treasure cave is strong and tightly shut. Without knowing the secret to opening it, the door cannot be opened. Next to the door is a strange rectangular password grid. According to the treasure-hunting manual, there is a ruby button on the left of each row and at the top of each column of the grid. Each button can be turned to the left or to the right. Each time a button is turned to the left, all numbers in the corresponding row or column increase by $1$. Each time a button is turned to the right, all numbers in the corresponding row or column decrease by $1$. Some positions in the grid are inlaid with emeralds. Only when the numbers at all emerald positions exactly match the password recorded on the map will the tightly shut door slowly open. The witch Gagool already knows the secret of opening the door. To stop the treasure hunters, she set the initial state of the grid to all $0$s. If the treasure hunters cannot quickly turn the buttons so that all emerald positions match the password exactly, a hidden mechanism will be triggered, causing a deadly attack.

Can you help the three treasure hunters open the door of the treasure cave?

Programming task: For the given password grid, determine whether there exists a sequence of ruby button rotations that yields the correct password at all emerald positions.

Input Format

The first line contains a positive integer $T$ ($T \le 5$), indicating there are $T$ test cases. For each test case, the first line contains $3$ positive integers $n$, $m$, and $k$, meaning the grid has $n$ rows and $m$ columns, with $0 < n, m, k \le 1000$. Rows are numbered $1, 2, \ldots, n$ from top to bottom; columns are numbered $1, 2, \ldots, m$ from left to right. The next $k$ lines each contain three integers $x$, $y$, $c$, indicating the position and required password value of an emerald in the grid: $x$ is the row index, $y$ is the column index, and $c$ is the required value at that position.

Output Format

For each test case, output one line: Yes if there exists a sequence of ruby button rotations that yields the correct password, or No if it is impossible.

2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 1

Yes
No

Hint

Constraints: For $100\%$ of the testdata, $1 \le n, m, k \le 1000$, $k \le n \times m$, $|c| \le 1,000,000$.

Translated by ChatGPT 5