#179. 鸦羽,成为我的刀刃吧!

鸦羽,成为我的刀刃吧!

题目描述

在最后的战斗中,露西亚丢失了自己的全部记忆。

为了找回露西亚的记忆,灰鸦小队的成员们找回了露西亚的记忆碎片。

但是不确定这些记忆碎片能否还原露西亚原本的记忆,身为灰鸦小队指挥官的你能判断露西亚能否恢复原本的记忆吗?

给定一个数n表示露西亚原来的记忆的种类,mm 表示灰鸦小队找到的记忆碎片的数量

随后是 mm 个记忆碎片,为大于 00 的正整数。(相同的记忆碎片最多有一对,其他的记忆碎片两两不同,对于这一对可以在一次中分别使用)

如果对于任意 [1,n][1,n] 的数字总是存在有任意kk (1km)(1\leq k \leq m)个记忆碎片的和与之相等(每个碎片对于每一个数字只能使用一次,每个碎片独立存在)则说明露西亚可以恢复原本的记忆。

此时露西亚将再次与你并肩作战,输出 “鸦羽,成为我的刀刃吧!”(不输出引号)。

否则,输出 “还不是最后。”(不输出引号)。

输入格式

第一行有两个数字 nnmm

接着是mm个数字,表示记忆碎片的种类。

输出格式

一句话“鸦羽,成为我的刀刃吧!”或者“还不是最后。”(没有引号)。

样例

样例一

输入

1 1
1

输出

鸦羽,成为我的刀刃吧!

样例二

输入

8 4
1 1 2 4

输出

鸦羽,成为我的刀刃吧!

样例三

输入

5 3
1 1 2

输出

还不是最后。

数据范围与提示

Tips:

由于记忆在构造体中是以二进制存储的,因此将n和每个记忆碎片转换为二进制对照思考会更简单。

对于样例二

转化为二进制:


8=10008=1000
1=00011=0001
2=00102=0010
4=01004=0100



1=11=1
2=22=2
3=1+23=1+2
4=44=4
5=1+45=1+4
6=2+46=2+4
7=2+4+17=2+4+1
8=1+1+2+48=1+1+2+4

因为上边的所有构造只使用了1241,2,4,11最多出现了两次;

由上可知,在样例二中只要出现过1241,2,4, (它们都是22的整数次幂) 且11出现两次,即可在此范围内构造出所有数字;

最后的11可以看作1=84211=8-4-2-1



对于样例三很显然无法构造出55

数据范围:

1n1e6 1 \leq n \leq 1e6

1mlog2n+1 1 \leq m \leq log_2 n+1

对于所有的记忆碎片:

1m1,m2,m3,...,mn1,mnn 1\leq m_1,m_2,m_3,...,m_{n-1},m_n \leq n