题目描述

小 H 想要装饰他的棋盘。

小 H 的棋盘有 $n\times m$ 个格子，构成一个 $n$ 行 $m$ 列的网格。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。围成这些格子的线段的交点称为格点，一共有 $(n+1)\times(m+1)$ 个格点。

下图展示了一个 $2\times3$ 的棋盘，其中黑点表示格点，每个格子的坐标标在其中心处。

小 H 的棋盘比较特殊：除了连接相邻格点的横向、纵向线段之外，每个格子内还恰好有一条连接两个格点的对角线。每个格子的对角线有两种可能：

• 从左上角连到右下角，称为 N 型；
• 从右上角连到左下角，称为 Z 型。

我们可以用一个长度为 $nm$、只包含字符 N 和 Z 的字符串来表示棋盘中所有格子的类型。具体地，先按从左到右的顺序连接第一行各格子的类型，再连接第二行，依此类推直到最后一行。这样得到的字符串称为这个棋盘的特征串。

因为想要装饰棋盘，小 H 希望给每个格点染上三种颜色之一。小 H 认为一种染色方案是美丽的，当且仅当任意两个被线段直接连接的格点颜色都不同。

下图展示了一种美丽的染色方案，它对应的特征串为 NNNZZZ。

现在，小 H 已经确定了一些格子的类型，并写下了对应的字符串 $S$。字符串 $S$ 只包含字符 N、Z 和 ?，其中 ? 表示该格子的类型尚未确定。

请你确定所有未确定格子的类型，使得最终棋盘至少存在一种美丽的染色方案。若存在方案，请输出字典序最小的特征串；若不存在方案，请输出 -1。

输入格式

第一行包含两个整数 $n,m$。

第二行包含一个长度为 $nm$ 的字符串 $S$，其中每个字符只可能是 N、Z 或 ?。

输出格式

如果存在合法方案，输出一行一个字符串，表示字典序最小的特征串。

如果不存在合法方案，输出一行 -1。

样例 1

输入

2 3
???ZZZ

输出

NNNZZZ

样例 2

输入

2 2
NZZZ

输出

-1

数据范围与子任务

对于所有数据，满足：