Pedestrian Crossing

Bytie and his friends want to cross the main street of Byteburg. The pedestrian crossing is painted with stripes that alternate in color: the first stripe is white, the second black, the third white, and so on. Bytie brags that he can walk straight across without ever stepping on a white stripe.

His shoe covers a segment of length $s$ measured along the walking direction, and every step moves him forward by exactly $k$. He may begin anywhere on the pavement of the near side, with his whole shoe resting on the pavement. From there he walks in equal steps of length $k$, straight across the crossing (perpendicular to the street). At no moment may his shoe overlap the interior of a white stripe, not even partially; the front or the back edge of the shoe is, however, allowed to touch the boundary of a white stripe. He may land on the same black stripe several times, and he may skip some black stripes entirely. After his final step his whole shoe must rest on the pavement of the far side.

Because the stripes were painted with uneven widths, the task is trickier than it sounds. Determine whether Bytie can cross the street as he claims.

The first line contains one integer $t$ ($1 \le t \le 10$), the number of test cases. Each test case is given on two lines. The first line holds three integers $s$, $k$, and $n$ ($1 \le s < k \le 10^9$, $2 \le n \le 500{,}000$): the shoe length, the step length, and the number of stripes. The second line holds $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^9$), the widths of the stripes in order. Stripe $1$ is white, stripe $2$ is black, stripe $3$ is white, and so on: odd-numbered stripes are white and even-numbered stripes are black.

For each test case print one line: TAK if Bytie can cross the street under the rules above, or NIE otherwise. (TAK and NIE are Polish for yes and no.)

The figure shows one possible way for Bytie to cross the street in the first sample test.