Description

一个n*n的棋盘。时刻0在位置(x,y)放置一个骑士。骑士在每个时刻可以按照
规则移动（在一个坐标上移动|2|，另一个坐标上移动|1|）。不过，这个棋盘比
较特殊。每个位置只在特定的时刻可以被使用。更准确地说，位置(i,j)能被使用
当且仅当当前时刻是Ki,j的倍数，其中Ki,j是位置(i,j)的已知属性。每一时刻骑士都会随机地选择并移动到一个可以被使用并且可达的位置。已 知骑士随机移动了T步，求在时刻T骑士有 可能在哪些位置出现。n <= 30, T <= 10^6。

Input

Output

Sample Input

Sample Output

Hint

Source