← 返回题目列表

Codeforces · 704/D

D. 美国队长

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

史蒂夫·罗杰斯对神盾局给他的新振金盾牌很着迷。它们都是无色的。共有 n 个屏蔽,第 i 个屏蔽位于坐标平面的 (xi,yi) 点。两个或多个屏蔽可能共享同一位置。

史蒂夫想要绘制所有这些盾牌。他将每个盾牌涂成红色或蓝色。将盾牌涂成红色需要 r 美元,而涂成蓝色则需要 b 美元。

此外,Steve 想要满足 m 个约束。第 i 个约束由三个整数 ti、li 和 di 提供:

- 如果 ti = 1,则 x = li 线上的红色和蓝色屏蔽数量之间的绝对差不应超过 di。
- 如果 ti = 2,则 y = li 线上的红色和蓝色屏蔽数量之间的绝对差不应超过 di。

Steve给你的任务是找到满足所有条件且总成本最小的画作。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100 000) - 分别是防护罩的数量和约束的数量。

第二行包含两个整数 r 和 b (1 ≤ r, b ≤ 109)。

接下来的 n 行包含盾牌坐标。这些行的第 i 行包含两个整数 xi 和 yi (1 ≤ xi, yi ≤ 109)。

接下来的 m 行包含约束。这些行的第 j 行包含三个整数 tj、lj 和 dj (1 ≤ tj ≤ 2、1 ≤ lj ≤ 109、0 ≤ dj ≤ n)。

输出

如果不可能满足所有约束,则在输出的第一行(也是唯一一行)中打印 -1。

否则,在输出的第一行中打印最小总成本。在第二行中打印一个长度为 n 的字符串,仅包含字母“r”和“b”。如果最佳答案中第 i 个屏蔽应涂成红色,则第 i 个字符应为“r”;如果应涂成蓝色,则第 i 个字符应为“b”。将防护罩涂成这些颜色的成本应等于您在第一行打印的最低成本。

如果存在多个最优解,则打印其中任意一个。

示例

输入 #1

5 6
8 3
2 10
1 5
9 10
9 10
2 8
1 9 1
1 2 1
2 10 3
2 10 2
1 1 1
2 5 2

输出 #1

25
rbrbb

输入 #2

4 4
7 3
10 3
9 8
10 3
2 8
2 8 0
2 8 0
1 2 0
1 9 0

输出 #2

-1