CF704D Captain America

在平面直角坐标系上有 $n$ 个点，你需要将每个点红蓝染色，将一个点染成红色的价格是 $r$，染成蓝色的价格是 $b$。 此外存在着 $m$ 条限制 $(t_i,l_i,d_i)$，$t_i=1$ 表示这条限制是“直线 $x=l_i$ 上的点染成两种颜色的点数之差的绝对值不得大于 $d_i$”，$t_i=2$ 表示这条限制是“直线 $y=l_i$ 上的点染成两种颜色的点数之差的绝对值不得大于 $d_i$”。 你需要在满足这些限制的情况下找到一种花费最少的染色方案，或者报告无解。

第一行两个整数 $n,m(1\le n,m\le 10^5)$。\ 第二行两个整数 $r,b(1\le r,b\le 10^9)$。\ 接下来 $n$ 行，每行两个整数 $x_i,y_i(1\le x_i,y_i\le 10^9)$ 描述一个点。\ 接下来 $m$ 行，每行三个整数 $t_i,l_i,d_i(1\le t_i\le 2,1\le l_i\le 10^9,0\le d_i\le n)$。

如果无解，输出 $-1$。 否则，第一行输出一个数字，表示最小花费，第二行输出一个长为 $n$ 的字符串，第 $i$ 个字符为 `r` 表示你将第 $i$ 个点染成红色，第 $i$ 个字符为 `b` 表示你将第 $i$ 个点染成蓝色。 如果有多个解，输出任意一个均可。

Translated By @[chenxi2009](/user/1020063)