Problem - 6139

> A young Jedi named Darth Vader, who was a pupil of mine until he turned to evil, helped the Empire hunt down and destroy the Jedi Knights. He betrayed and murdered your father. Now the Jedi are all but extinct."
>
> --- Obi-Wan Kenobi, to Luke Skywalker

> The Jedi Purge was the period in which the Jedi Order was destroyed by the Sith and the Jedi were hunted by the Galactic Empire to near-extinction.
>
> --- Wookieepedia

In the Jedi Temple, the $501$-st Legion headed by Darth Vader are having an intense battle with the Jedi. The Jedi Temple can be seen as an $n \times m$ matrix. There are Meditations that can enhance the force and pollutant sources from the dark side that weaken the force. There are some crystals in the Temple. Vader and Jedi master Yoda are playing a game, which is moving the crystals in turns.

Each turn, the player can choose a cell $(x, y)$ with crystals. Suppose that there are $w$ crystals in $(x, y)$, the player can pick up $t (1 \le t \le w)$ crystals. If there is a Meditation in $(x, y)$, because of the amazing power of Meditation, the player can produce $t$ extra crystals: he can place $t$ crystals in $(x + 1, y)$ and $t$ crystals in $(x, y + 1)$. Otherwise (there is no Mediation in $(x, y)$), the player can just place $t$ crystals in $(x + 1, y)$ *or* place $t$ crystals in $(x, y + 1)$.

However, if $t$ crystals are put into a cell $(x, y)$ where there is a pollutant source, $\lceil \frac{t}{2} \rceil$ crystals will be destroyed and only $\lfloor \frac{t}{2} \rfloor$ are saved.

Besides, there is a super pollutant source in $(n, m)$, and it will destroy all crystals put into $(n, m)$. To control this darkness, there is a Meditation in $(n - 1, m)$.

In addition, there is a force field outside the Jedi Temple, which means that you can not move any crystals outside the matrix. That is to say:

- If you should put $k$ crystals into $(x + 1, y)$ and $k$ crystals into $(x, y + 1)$, but $(x + 1, y)$ is outside the matrix, then you can only put $2k$ crystals into $(x, y + 1)$. Similarly, you can only put $2k$ crystals into $(x + 1, y)$ if $(x, y + 1)$ is outside the matrix.
- If you can choose to put $k$ crystals into $(x + 1, y)$ or $(x, y + 1)$ but one of them is outside the matrix, you can only put the crystals into the other one.

The one who cannot move any crystal will lose the game. Both Darth and Yoda are smart and will always choose the optimal strategy. Now, Vader is playing first, can he win the game and evade the Jedi Temple?

Because of the collision of Meditations and pollutant sources, for every pair of Meditations $(x, y)$ and pollutant sources $(a, b)$, $$\max(\left| (x-a)+(y-b) \right|, \left| (x-y)-(a-b)\right|)$$ is constrained to be an odd number.

The first line of the input contains an integer $T$, denoting the number of test cases.

For each test case, the first line contains two integers $n, m$ ($1\le n,m\le 10^3$).

The next line contains an integer $k$ ($0\le k\le 5\times10^5$), denoting the number of places containing crystals.

Each of the following $k$ lines contains three integers $x, y, w$, representing that there are $w$ ($1\le w\le 10^9$) crystals in cell $(x, y)$.

The next line contains an integer $t$ ($0\le t\le 5\times10^5$).

Each of the following $t$ lines contains two integer $x, y$, which means that there is a Meditation in $(x, y)$.

The next line contains an integer $s$ ($0\le s\le 5\times10^5$).

Each of the following $s$ lines contains two integer $x, y$, which means that there is a pollutant sources in $(x, y)$.

All $x$ and $y$ satisfy $1 \le x \le n, 1 \le y \le m$.

Galaxy at War