D. Капитан Америка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Стив Роджерс в восторге от новых щитов, которые ему выдали в S.H.I.E.L.D. Осталось только их раскрасить. Всего щитов n, i-й из которых расположен в точке (xi, yi) координатной плоскости. Вполне возможно, что два или более щита расположены в одной точке.

Стив хочет покрасить каждый щит в красный или синий цвет. Покраска щита в красный стоит r долларов, а покраска в синий стоит b долларов.

Дополнительно покраска Стива должна удовлетворять m условиям. Каждое условие описывается тремя целыми числами ti, li и di:

  • Если ti = 1, то модуль разницы между количеством красных и количеством синих щитов на прямой x = li не должен превосходить di.
  • Если ti = 2, то модуль разницы между количеством красных и количеством синих щитов на прямой y = li не должен превосходить di.

Стив поручил вам найти корректную раскраску минимальной стоимости.

Входные данные

В первой строке входных данных записаны два целых числа 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-й из этих символов должен быть равен «r», если i-й щит следует покрасить в красный цвет в оптимальном ответе, и «b», если его следует покрасить в синий.

Если оптимальных решений несколько, выведите любое из них.

Примеры
Входные данные
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
Выходные данные
25
rbrbb
Входные данные
4 4
7 3
10 3
9 8
10 3
2 8
2 8 0
2 8 0
1 2 0
1 9 0
Выходные данные
-1