Теплицы фермера Джона
(Время: 2 сек. Память: 32 Мб Сложность: 47%)
На участке фермера Джона растут N растений: i-е из них имеет координаты (Xi, Yi) и вид Ci, выраженный строчной буквой латинского алфавита. Будем считать, что растение является точкой на плоскости участка.
Из-за приближающейся зимы Джон хочет построить по одной теплице для каждого вида, который есть у него на участке.
- Каждая такая теплица должна быть прямоугольником, со сторонами, параллельными осям координат. При этом допускаются прямоугольники нулевой площади;
- Все растения одного вида должны быть в одной теплице;
- Теплица должна содержать растения только одного вида;
- Никакие две теплицы не должны пересекаться, то есть не должны иметь общую точку.
Выясните, можно ли построить теплицы, выполняя эти условия.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число T — количество наборов входных данных (1 ⩽ T ⩽ 30 000).
Каждый набор данных начинается со строки, содержащей целое число N — количество растений (1 ⩽ N ⩽ 200 000).
В следующих N строках содержатся два целых числа Xi и Yi, а также тип Ci (0 ⩽ Xi, Yi ⩽ 109).
Гарантируется, что сумма значений N в одном тесте не превосходит 200 000.
Выходные данные
В выходной файл OUTPUT.TXT на каждый набор входных данных выведите ответ в отдельной строке.
Если возможно построить теплицы, то выведите «Yes», а если невозможно, то «No».
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
2
1 1 a
2 2 b
3
1 3 c
3 1 c
2 2 d
3
3 1 e
1 3 e
1 1 f
4
4 4 g
5 5 g
1 1 h
8 2 h | Yes
No
No
Yes |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
