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.
## Input
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_).
## Output
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.
[samples]
史蒂夫·罗杰斯对神盾局交给他的新型振金盾牌非常着迷。这些盾牌都未上色。总共有 #cf_span[n] 个盾牌，第 #cf_span[i] 个盾牌位于坐标平面上的点 #cf_span[(xi, yi)] 处。可能存在两个或多个盾牌位于同一位置。
史蒂夫希望将所有这些盾牌上色。他将每个盾牌涂成红色或蓝色。将一个盾牌涂成红色需要花费 #cf_span[r] 美元，涂成蓝色需要花费 #cf_span[b] 美元。
此外，史蒂夫希望满足 #cf_span[m] 个约束条件。第 #cf_span[i] 个约束由三个整数 #cf_span[ti]、#cf_span[li] 和 #cf_span[di] 给出：
你被赋予了任务，找出一种满足所有条件且总成本最小的上色方案。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 100 000]）——分别表示盾牌数量和约束数量。
第二行包含两个整数 #cf_span[r] 和 #cf_span[b]（#cf_span[1 ≤ r, b ≤ 10^9]）。
接下来的 #cf_span[n] 行包含盾牌的坐标。第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ 10^9]）。
接下来的 #cf_span[m] 行包含约束条件。第 #cf_span[j] 行包含三个整数 #cf_span[tj]、#cf_span[lj] 和 #cf_span[dj]（#cf_span[1 ≤ tj ≤ 2, 1 ≤ lj ≤ 10^9, 0 ≤ dj ≤ n]）。
如果无法满足所有约束条件，请在输出的第一行且仅一行中打印 _-1_。
否则，在输出的第一行打印最小总成本。在第二行打印一个长度为 #cf_span[n] 的字符串，仅由字母 '_r_' 和 '_b_' 组成。第 #cf_span[i] 个字符应为 '_r_'，表示第 #cf_span[i] 个盾牌在最优解中应涂成红色；若应涂成蓝色，则为 '_b_'。这些颜色的涂色成本应等于你在第一行打印的最小成本。
如果存在多个最优解，输出其中任意一个即可。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 100 000]）——分别表示盾牌数量和约束数量。第二行包含两个整数 #cf_span[r] 和 #cf_span[b]（#cf_span[1 ≤ r, b ≤ 10^9]）。接下来的 #cf_span[n] 行包含盾牌的坐标。第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ 10^9]）。接下来的 #cf_span[m] 行包含约束条件。第 #cf_span[j] 行包含三个整数 #cf_span[tj]、#cf_span[lj] 和 #cf_span[dj]（#cf_span[1 ≤ tj ≤ 2, 1 ≤ lj ≤ 10^9, 0 ≤ dj ≤ n]）。
## Output
如果无法满足所有约束条件，请在输出的第一行且仅一行中打印 _-1_。否则，在输出的第一行打印最小总成本。在第二行打印一个长度为 #cf_span[n] 的字符串，仅由字母 '_r_' 和 '_b_' 组成。第 #cf_span[i] 个字符应为 '_r_'，表示第 #cf_span[i] 个盾牌在最优解中应涂成红色；若应涂成蓝色，则为 '_b_'。这些颜色的涂色成本应等于你在第一行打印的最小成本。如果存在多个最优解，输出其中任意一个即可。
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of shields and constraints.
Let $ r, b \in \mathbb{Z}^+ $ denote the cost of painting a shield red and blue, respectively.
Let $ S = \{ (x_i, y_i) \mid i \in \{1, \dots, n\} \} $ be the set of shield positions.
Let $ C = \{ (t_j, l_j, d_j) \mid j \in \{1, \dots, m\} \} $ be the set of constraints, where:
- $ t_j \in \{1, 2\} $: type of constraint (1 = Manhattan distance ≤ $ l_j $, 2 = Manhattan distance ≥ $ l_j $),
- $ l_j \in \mathbb{Z}^+ $: distance threshold,
- $ d_j \in \{0, \dots, n\} $: required number of red shields in the region.
Let $ p_i \in \{0, 1\} $ be a binary variable: $ p_i = 0 $ if shield $ i $ is painted blue, $ p_i = 1 $ if red.
**Constraints**
For each constraint $ j \in \{1, \dots, m\} $:
- Define region $ R_j = \{ i \in \{1, \dots, n\} \mid \text{Manhattan}( (x_i, y_i), (0, 0) ) \leq l_j \} $ if $ t_j = 1 $,
or $ R_j = \{ i \in \{1, \dots, n\} \mid \text{Manhattan}( (x_i, y_i), (0, 0) ) \geq l_j \} $ if $ t_j = 2 $.
- Then: $ \sum_{i \in R_j} p_i = d_j $.
**Objective**
Minimize total cost:
$$
\sum_{i=1}^n \left( p_i \cdot r + (1 - p_i) \cdot b \right)
= \sum_{i=1}^n b + \sum_{i=1}^n p_i (r - b)
$$
Subject to the above constraints.
If no assignment satisfies all constraints, output $-1$.