CF704D.Captain America

Steve Rogers is fascinated with new vibranium shields S.H.I.E.L.D gave him. They're all uncolored. There are n shields in total, the i-th shield is located at point (x__i, y__i) of the coordinate plane. It's possible that two or more shields share the same location.

Steve wants to paint all these shields. He paints each shield in either red or blue. Painting a shield in red costs r dollars while painting it in blue costs b dollars.

Additionally, there are m constraints Steve wants to be satisfied. The i-th constraint is provided by three integers t__i, l__i and d__i:

• If t__i = 1, then the absolute difference between the number of red and blue shields on line x = l__i should not exceed d__i.
• If t__i = 2, then the absolute difference between the number of red and blue shields on line y = l__i should not exceed d__i.

Steve gave you the task of finding the painting that satisfies all the condition and the total cost is minimum.

史蒂夫·罗杰斯对神盾局新提供的振金盾牌非常着迷。这些盾牌目前均未上色。总共有 $n$ 个盾牌，其中第 $i$ 个盾牌位于坐标平面上的点 $(x_i,\,y_i)$ 处。可能存在两个或更多盾牌位于同一位置的情况。

史蒂夫希望为所有这些盾牌上色，每个盾牌只能涂成红色或蓝色。将一个盾牌涂成红色的花费为 $r$ 美元，涂成蓝色的花费为 $b$ 美元。

此外，还有 $m$ 个约束条件需要满足。第 $i$ 个约束由三个整数 $t_i$、$l_i$ 和 $d_i$ 给出：

• 若 $t_i = 1$，则直线 $x = l_i$ 上红色盾牌数量与蓝色盾牌数量之差的绝对值不得超过 $d_i$；
• 若 $t_i = 2$，则直线 $y = l_i$ 上红色盾牌数量与蓝色盾牌数量之差的绝对值不得超过 $d_i$。

史蒂夫委托你找出一种满足所有约束条件且总花费最小的上色方案。

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the number of shields and the number of constraints respectively.

The second line contains two integers r and b (1 ≤ r, b ≤ 109).

The next n lines contain the shields coordinates. The i-th of these lines contains two integers x__i and y__i (1 ≤ x__i, y__i ≤ 109).

The next m lines contain the constrains. The j-th of these lines contains three integers t__j, l__j and d__j (1 ≤ t__j ≤ 2, 1 ≤ l__j ≤ 109, 0 ≤ d__j ≤ n).

输入的第一行包含两个整数 $n$ 和 $m$（$1 ≤ n, m ≤ 100\,000$），分别表示护盾的数量和约束条件的数量。

第二行包含两个整数 $r$ 和 $b$（$1 ≤ r, b ≤ 10^9$）。

接下来的 $n$ 行描述护盾的坐标。其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 ≤ x_i, y_i ≤ 10^9$）。

接下来的 $m$ 行描述约束条件。其中第 $j$ 行包含三个整数 $t_j$、$l_j$ 和 $d_j$（$1 ≤ t_j ≤ 2$，$1 ≤ l_j ≤ 10^9$，$0 ≤ d_j ≤ n$）。

If satisfying all the constraints is impossible print -1 in first and only line of the output.

Otherwise, print the minimum total cost in the first line of output. In the second line print a string of length n consisting of letters 'r' and 'b' only. The i-th character should be 'r' if the i-th shield should be painted red in the optimal answer and 'b' if it should be painted blue. The cost of painting shields in these colors should be equal the minimum cost you printed on the first line.

If there exist more than one optimal solution, print any of them.

如果无法满足所有约束条件，则在输出的第一行且仅第一行中打印 -1。

否则，在输出的第一行打印最小总成本。在第二行打印一个长度为 $n$ 的字符串，该字符串仅由字母 'r' 和 'b' 组成。其中第 $i$ 个字符应为 'r'，表示在最优解中第 $i$ 个盾牌应涂成红色；应为 'b'，表示应涂成蓝色。按此着色方案所得到的涂色成本应等于第一行所打印的最小成本。

若存在多个最优解，输出任意一个即可。