2524: 解密

jsoi 的训练模式是每天做一套模拟题,因为现在参加 jsoi 的同学太多了,每天早
上发题就变成一件让人非常不爽的事,lhc 觉得每天都要用 U 盘拷了题目到各机房发题
很磨很麻烦,于是决定前一天晚上把组好的题加密然后放在 jsoi 群共享里,让大家第
二天早上自带题目,到时间只要公布密码就可以了。不过很遗憾的是,第一次实践就出
了问题:第二天早上 lhc 忘记密码了 ! 现在 lhc 告诉你他的密码串的加密方式,解密
的工作就让你自己完成吧。
lhc设定的密码P一定是一个二进制串,他事先在群里公布了另一个数字串Q,P到Q
的转换方法如下:Q[i] = P[i-1] + P[i] + P[i+1] 例如:P = 011100011,那么Q =
123210122。对于边界情况忽略,即Q[1] = P[1] + P[2], Q[N] = P[N] + P[N-1]。现
在你知道了Q,但是题目的密码是P,你需要求出P。因为P的首位是未知的,可能是0,
也可能是1,所以存在不同2种的解密结果,你需要把这两种情况都输出(除非你不想做
题了 ☺)。

输入包含一行字符串 Q,lhc 事先公布的数字串。

输出两行,第一行表示当 P 的首位为 0 的解密信息,第二行表示当 P 的首位为 1 的
解密信息。如果有无解情况输出“NONE”。输入数据保证 P 的长度不会超过 50 位。

123210122

011100011
NONE