← 返回题目列表

Codeforces · 1662/M

M. 瓶子布置

中文机器翻译题面 查看原题

加布里埃拉受命组织一场著名的品酒活动,届时将有 $$$m$$$ 评论家参加。展出的葡萄酒有$$$n$$$不同品种,每种葡萄酒可以是红葡萄酒,也可以是白葡萄酒。

葡萄酒将装在桌子上排成一排的 $$$n$$$ 瓶中,为了方便起见,每个评论家都会从连续的瓶子间隔中啜饮:也就是说,他/她将准确品尝位于 $$$a, \, a + 1, \, \dots, \, b$$$ 位置的瓶子,其中一些 $$$1 \le a \le b \le n$$$。间隔时间取决于评论家,评论家会根据自己的喜好当场选择。事实上,第 $$$i$$$ 评论家 ($$$1 \le i \le m$$$) 要求他/她想要品尝准确的 $$$r_i$$$ 红葡萄酒和 $$$w_i$$$ 白葡萄酒。

加布里埃拉尚未选择将有多少瓶红酒和白葡萄酒,以及它们出现的顺序。帮助她找到一种满足所有评论家要求的排列(即一系列 $$$n$$$ 瓶红葡萄酒或白葡萄酒),或者声明不存在这样的排列。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。 $$$t$$$ 测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 100$$$)——葡萄酒的瓶数和评论家的数量。

接下来的 $$$m$$$ 行包含两个整数 $$$r_i$$$ 和 $$$w_i$$$ ($$$0 \le r_i, \, w_i \le 100$$$, $$$r_i + w_i \ge 1$$$) — 第 $$$i$$$ 评论家想要品尝的红葡萄酒和白葡萄酒的数量。

输出

对于每个测试用例,如果至少存在一个解决方案,则打印由字符 R 和 W 组成的长度为 $$$n$$$ 的字符串,其中第 $$$j$$$ 个字符 ($$$1 \le j \le n$$$) 表示排列中第 $$$j$$$ 瓶中葡萄酒的类型(R 代表红色,W 代表白色)。如果有多个解决方案,请打印其中一个。

如果不存在解,则打印字符串 IMPOSSIBLE。

示例

输入 #1

3
5 3
1 0
3 2
2 2
4 3
2 1
1 1
0 3
3 2
0 2
0 3

输出 #1

RWRRW
IMPOSSIBLE
WWW

注意

在第一个测试用例中,需要安排 $$$n = 5$$$ 瓶葡萄酒和 $$$m = 3$$$ 评论家。 RWRRW的安排满足了三位批评家的要求。确实:

- 第一个评论家可以选择区间 $$$[3, \, 3]$$$,其中恰好包含一瓶红酒(注意 $$$[1, \, 1]$$$ 和 $$$[4, \, 4]$$$ 是其他有效选择);
- 第二个评论家可以选择区间$$$[1, \, 5]$$$,其中包含$$$3$$$瓶红酒和$$$2$$$瓶白葡萄酒;
- 第三个评论家可以选择区间$$$[2, \, 5]$$$,其中包含$$$2$$$瓶红酒和$$$2$$$瓶白葡萄酒。