This page is still under construction.

Parts of this page are still being built. What you see may change.

(K, N)-Knight

Time limit1sMemory limit128 MB

Summary
Given K, N and two squares, decide whether a generalized knight that jumps K and N squares in either order can travel between them.
Level

Medium7 of 10

Topics
Math, Number theory, Graph, Implementation
Solved
No attempts yet

Problem

On an infinitely large chessboard you are given two squares (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2). Write a program that decides whether a (K,N)(K, N)-knight can travel from (x1,y1)(x_1, y_1) to (x2,y2)(x_2, y_2).

A (K,N)(K, N)-knight moves much like an ordinary knight. In a single move it can jump to a square that is KK columns and NN rows away, or NN columns and KK rows away. In other words, from (x,y)(x, y) it moves to one of (x±K,y±N)(x \pm K, y \pm N) or (x±N,y±K)(x \pm N, y \pm K). The ordinary chess knight is a (2,1)(2, 1)-knight (equivalently a (1,2)(1, 2)-knight).

Input

The first line contains the number of test cases TT (1≤T≤20,0001 \le T \le 20{,}000). Each test case is a single line with six integers KK, NN, x1x_1, y1y_1, x2x_2, y2y_2 separated by spaces. (0≤K,N≤1090 \le K, N \le 10^9, K+N>0K + N > 0, −109≤x1,y1,x2,y2≤109-10^9 \le x_1, y_1, x_2, y_2 \le 10^9)

Output

For each test case, print TAK if the (K,N)(K, N)-knight can move from (x1,y1)(x_1, y_1) to (x2,y2)(x_2, y_2), or NIE otherwise. Print one answer per line.

Examples1

  1. Example 1

    Input
    3
    2 1 0 0 3 3
    1 1 1 1 1 2
    1 0 2 3 4 6
    
    Expected output
    TAK
    NIE
    TAK