AE2B - (K,N)-Knight

no tags 

Bytean chess is one of the most peculiar variants of chess in the world. Playing each match is a major difficulty, because the game is played on an infinite chessboard. The basic ability learnt by young enthusiasts of Bytean chess is considering all possible situations on a chessboard after millions of moves. To perform this, they need to know whether a given chess piece can get from one given square to another one.

The most powerful chess piece in Bytean chess is a (K, N)-knight. Its moves resemble the moves of a knight in traditional chess. Each of its moves consists of: either moving K squares vertically and afterwards N squares horizontally, or moving N squares vertically and afterwards K squares horizontally. The knight from traditional chess can therefore be thought of as (2, 1)-knight or (1, 2)-knight.

The task is to verify, for two given squares of the chessboard, if a (K, N)-knight can get from the first square to the second one (the number of necessary moves is not important).

Input

The first line of the standard input contains one integer T (1 ≤ T ≤ 20000) denoting the number of test cases. Each of the following T lines contains a description of a single test case in the form of six integers K, N, x1, y1, x2, y2 (0 ≤ K, N ≤ 109, K + N > 0, -109 ≤ x1, y1, x2, y2 ≤ 109) separated by single spaces. K and N describe the possible moves of the knight. The knight starts its movement in square (x1, y1). We would like to check if it can get to square (x2, y2).

Output

For each test case exactly one line should be written to the standard output. It should contain a word TAK (meaning YES) or NIE (meaning NO) depending on whether a (K, N)-knight starting from square (x1, y1) can get to square (x2, y2).

Example

For the input data:

3
2 1 0 0 3 3
1 1 1 1 1 2
1 0 2 3 4 6

the correct result is:

TAK
NIE
TAK

Task author: Jakub Onufry Wojtaszczyk.


hide comments
Vladimir Kirichenkoff: 2021-07-29 17:04:53

If you're getting WA, please, ensure that first 2 cases are solved correctly.

Vladimir Kirichenkoff: 2021-07-29 17:00:23

To solve this task, perform the next steps:
1. Solve the task for cases when k == 0 or n == 0.
2. Solve the task for cases when k == n.
3. Solve how to transform other cases to one of cases above.

vincecao: 2017-12-18 12:07:23

WA for several times and don't know why :(
I have considered the 0 cases. can anyone give some tricky test cases?

krist7599555: 2016-12-20 13:16:29

so sadly for case K==0 && N==0

Bhavik: 2014-02-16 12:34:44

knight tour problem...:)

ওয়াসী (Wasi): 2013-07-16 08:16:51

Is there any chance of getting WA instead of TLE while the code actually gets TLE?
my last py3 submission(same code that got WA couple of time)got TLE.
i have wasted hours submitting py3 codes and getting WA yet the c++ translation got AC :(

unXled: 2012-06-27 05:04:10

take care of dividing by zero..costed me lot of SIGFPE....

nitish_goyal28: 2011-07-24 07:35:48

more test cases please...

Ankit Gupta: 2011-06-23 13:31:21

my submission id is 5282393
plz tell where i'm getting d wa


Added by:Race with time
Date:2009-05-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Algorithmic Engagements 2009