#P18139. Breaking Bad

Breaking Bad

Breaking Bad

Walt、Jesse、Mike、Saul和Todd把一片地区划分成n×n个格子,第i行第j列的收入为a_{i,j}美元。

他们要选出n个格子,要求每行、每列恰好选择一个。设所选格子的收入总和为S。把钱平均分给五人后,余下的S mod 5美元会捐给Ted Beneke。

请求出所有可能的捐款金额,也就是所有可能的S mod 5。

输入格式

第一行一个整数n,1≤n≤1000。

接下来n行,每行n个整数a_{i,j},满足0≤a_{i,j}≤4。

输出格式

输出恰好由5个大写字符Y或N组成的字符串。若余数i可以达到,则第i+1个字符为Y,否则为N;五个字符依次对应余数0、1、2、3、4。

样例 1

2
0 4
4 0
YNNYN

选择主对角线的总和为0,选择另一条对角线的总和为8,模5为3。

样例 2

2
1 1
1 1
NNYNN

每种合法选法的总和都是2。