408737: GYM103286 B Рудольф и генераторы тьмы

B. Рудольф и генераторы тьмыограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Рудольф попал в противоположное измерение, где всегда светло, а вместо лампочек используют генераторы тьмы, расположенные на огромной прямоугольной площадке, представляющей собой клетчатое поле. Каждый генератор характеризуется координатами клетки ($$$X_i$$$, $$$Y_i$$$), в которой он расположен, и мощностью $$$D_i$$$. В клетке ($$$X_i$$$, $$$Y_i$$$) генератор создает тьму, равную $$$D_i$$$; в клетках вокруг генератора (в восьми соседних клетках; клетка является соседней, если граничит с текущей по стороне или по углу), создается тьма равная $$$D_i-1$$$, в клетках вокруг этих клеток тьма равна $$$D_i-2$$$ и так далее, пока тьма не достигнет нуля (смотрите пример в примечании). Если на какую-то клетку воздействуют нескольких генераторов, то их тьма складывается.

Рудольф хотел отдохнуть в тени, но внезапно обнаружил, что в этом измерении он существует сразу в форме $$$M$$$ тёмных Рудольфов. Каждый из них имеет порог тьмы, при котором он может существовать. То есть каждому Рудольфу нужно находиться в клетке, в которой тьма не меньше определённого значения. В каждой клетке может находиться только один тёмный Рудольф. Помогите Рудольфу разместить свои сущности либо выясните, что это невозможно.

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

Первая строка содержит число $$$N$$$ $$$(1 \leq N \leq 1000)$$$ — количество генераторов тьмы.

Следующие $$$N$$$ строк содержат по три целых числа $$$X_i$$$, $$$Y_i$$$, $$$D_i$$$ $$$(0 \leq X_i, Y_i \leq 1000)$$$, $$$(1 \leq D_i \leq 1000)$$$ — координаты и мощности генераторов соответственно.

Следующая строка содержит число $$$M$$$ $$$(1 \leq M \leq 1000)$$$ — количество темных Рудольфов.

Следующая строка содержит $$$M$$$ целых чисел $$$R_j$$$ $$$(1 \leq R_j \leq 100000)$$$ — минимальное количество тьмы, в которой может существовать $$$j$$$-й тёмный Рудольф.

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

Если разместить всех Рудольфов невозможно, выведите «NO».

В противном случае выведите «YES», затем выведите $$$M$$$ строк. В каждой строке выведите два целых числа $$$X_i$$$, $$$Y_i$$$ $$$(0 \leq X_i, Y_i \leq 1000)$$$ — координаты $$$i$$$-го Рудольфа. Если ответов несколько, выведите любой.

ПримерыВходные данные

2
1 1 3
4 6 2
12
2 2 2 1 2 2 3 1 2 2 2 2

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

YES
1 0
4 6
2 2
4 7
1 2
0 2
1 1
3 7
2 1
0 1
0 0
2 0

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

3
0 0 5
3 0 4
5 5 7
5
6 3 9 2 9

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

YES
1 1
1 0
2 2
3 2
2 1

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

1
2 2 3
4
2 3 3 2

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

NO

Примечание

Пример первого теста приведен на рисунке. Синие клетки — расположение генераторов. Цифры обозначают мощность тьмы в клетках.