题目描述

$\red{namespace\_std }$这天打开了一本古老的算法书，上面描述了一个经典的 $\red{NP }$问题：

给定一个集合，其元素为$\red{\{a[1],a[2],...,a[n]\}，}$其中$\red{a[1]+a[2]+...+a[n]}$为偶数，你需要找到一组$\red{c[1],c[2],...,c[n]∈}$$\red{\{-1,1\}}$ ，使得$\red{Σa[i]c[i]=0}$。

$\red{namespace\_std }$发现这是一个很困难的问题，因此他想加一些限制。他限制$\red{\{a[1],a[2],...,a[n]\}}$是$\red{\{1,2,...,m\}}$ 的一个子集。

他发现这还是一个很困难的问题，因此他又限制$\red{[2m/3]<n<=m}$。

这个问题还是很困难，但他作为一名混乱邪恶的出题人，已经不想再弱化这个问题了……

因此，这个问题就交给你了。

你需要判断这个问题是否有解，如果有解则还要输出一组合法的$\red{c[i]}$。

输入格式

第一行输入两个正整数$\red{n,m}$。

第二行输入$\red{n}$个正整数$\red{a[1],a[2],...,a[n]}$。

保证$\red{\{a[1],a[2],...,a[n]\}}$是$\red{\{1,2,...,m\}}$的一个子集，$\red{a[1]+a[2]+...+a[n]}$为偶数，且$\red{[2m/3]<n<=m}$。

输出格式

如果问题有解，请输出一行 "$\red{NP-Hard solved}$"，并在接下来一行输出$\red{n}$个$\red{1}$或$\red{-1，}$表示你找到的解中的$\red{c[i]}$ 。如果有多种可行的$\red{c[i]，}$你只需要输出任意一种。

否则只需要输出一行 "$\red{Chaotic evil}$"。

样例

输入样例

6 8
1 6 2 5 4 8

输出样例

NP-Hard solved
1 -1 -1 -1 1 1

提示

样例解释

$\red{1-6-2-5+4+8=0，}$因此$\red{c=\{1,-1,-1,-1,1,1\}}$是一组合法的方案。

同理，$\red{c=\{-1,1,1,1,-1,-1\}}$也是一组合法的方案。

数据范围

对于 $\red{12\% }$的数据，$\red{m<=20 }$。

对于 $\red{28\% }$的数据，$\red{m<=300 }$。

对于 $\red{44\% }$的数据，$\red{m<=1000 }$。

对于 $\red{56\% }$的数据，$\red{m<=10^5 }$。

另有 $\red{8\% }$的数据，$\red{m=n }$。

另有 $\red{16\% }$的数据，保证$\red{n<=m-5}$。

对于 $\red{100\% }$的数据，$\red{3<=n<=m<=10^6，}$保证$\red{\{a[1],a[2],...,a[n]\}}$是$\red{\{1,2,...,m\}}$的一个子集， $\red{\{a[1],a[2],...,a[n]\}}$为偶数，且$\red{[2m/3]<n<=m}$。