史蒂夫·罗杰斯对神盾局给他的新振金盾牌很着迷。它们都是无色的。共有 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