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