SP4302 AE2B - (K,N)-Knight

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, x $ _{1} $ , y $ _{1} $ , x $ _{2} $ , y $ _{2} $ (0 ≤ K, N ≤ 10 $ ^{9} $ , K + N > 0, -10 $ ^{9} $ ≤ x $ _{1} $ , y $ _{1} $ , x $ _{2} $ , y $ _{2} $ ≤ 10 $ ^{9} $ ) separated by single spaces. K and N describe the possible moves of the knight. The knight starts its movement in square (x $ _{1} $ , y $ _{1} $ ). We would like to check if it can get to square (x $ _{2} $ , y $ _{2} $ ). 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 (x $ _{1} $ , y $ _{1} $ ) can get to square (x $ _{2} $ , y $ _{2} $ ). 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._

N/A

N/A