定义两个区间冲突当且仅当它们的交区间的长度大于0且分别小于两个区间的长度。也就是说区间的包含、相接、相离关系都不算冲突。

给定m个区间，请将其分为两个集合，使得每个集合内的区间不冲突。

第一行n m表示区间的范围以及区间的个数

接下来m行每行两个整数l,r描述一个区间[l,r]

如果无解则输出“NIE”

如果有解，输出m行，每行为N或S，相同字母对应的区间分在同一集合。如果有多解，请输出任意一组即可

30%：$1\leq n,m\leq 2\times 10^3$
65%：$1\leq n,m\leq 2\times 10^4$
100%：$1\leq n,m\leq 2\times 10^5$，$1\leq l\leq r\leq m$