409363: GYM103491 E Проводимость

E. Проводимостьограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

14 февраля в Силаэдре будет проводиться олимпиада по информатике. Условия составлены, тесты подготовлены, авторские решения написаны. Но вот беда: кто-то подметал серверную перед олимпиадой и случайно порвал интернет-кабель, который шел к тестирующему серверу!

Чтобы решить проблему, Владимир Михайлович, системный администратор школы, достал свою огромную коробку с проводами. Владимир Михайлович попал в поистине патовую ситуацию, ведь в коробке лежит целых $$$n$$$ проводов! Владимир Михайлович решил сделать цепь из проводов, которая начинается разъемом разъемом P (папа) и кончается разъемом M (мама). Для этого он может брать два провода и соединять их концами М (мама) и P (папа). В коробке лежат провода с концами M и P, M и M, а также P и P.

Также у каждого провода есть порядковый номер состоящий из китайского иероглифа, ведь именно в Китае провода были произведены. Известно, что иероглифы образуют перестановку первых n иероглифов в китайском алфавите. Чем меньше лексикографически строка, получившаяся, если выписать все иероглифы от начала (от конца цепи P) до конца цепи (до конца цепи M), тем быстрее будет интернет. Владимир Михайлович хочет обеспечить максимально быстрое соединение, при этом длина цепочки должна быть хотя бы $$$k$$$, ведь иначе она не дотянется до сервера. Помогите Владимиру Михайловичу подключить сервер к интернету!

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

В первой строке вводится два числа $$$n$$$ и $$$k$$$ - количество проводов в коробке и требуемая длина цепи из проводов. $$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq 10^{18}$$$.

Во последующих $$$n$$$ строках вводится два символа $$$t_{start}$$$ и $$$t_{end}$$$, каждый из которых - это буква «M» или «P» - вид концов провода, и два числа $$$L_i$$$ и $$$o_i$$$. первое число $$$1 \leq L_i \leq 10^9$$$ задает длину провода, второе число $$$1 \leq o_i \leq n$$$ - порядковый номер иероглифа на проводе в китайском алфавите.

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

В первой строке выведите «YES», если Владимир Михайлович сможет выбрать нужное ему подмножество проводов из коробки, и «NO» иначе.

Во второй строке выведите иероглифы на проводах начиная с начала цепи (от P) до конца цепи (до M).

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача	Баллы	Ограничения	Необходимые подзадачи	Информация о проверке
1	5	$$$1 \leq n \leq 2 * 10^5$$$, $$$t_{start}^i \neq t_{end}^i$$$		первая ошибка
2	5	$$$1 \leq n \leq 7$$$		первая ошибка
3	10	$$$1 \leq n \leq 17$$$	2	первая ошибка
4	20	$$$1 \leq n \leq 300$$$, $$$t_{start}^i = t_{end}^i$$$		первая ошибка
5	3	$$$1 \leq n \leq 300$$$	2-4	первая ошибка
6	20	$$$1 \leq n \leq 3000$$$, $$$t_{start}^i = t_{end}^i$$$	4	первая ошибка
7	5	$$$1 \leq n \leq 3000$$$	2-6	первая ошибка
8	30	$$$1 \leq n \leq 2 * 10^5$$$, $$$t_{start}^i = t_{end}^i$$$	4,6	первая ошибка
9	2	$$$1 \leq n \leq 2 * 10^5$$$	1-8	первая ошибка

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

4 13
M P 7 2
M M 2 1
P P 10 4
P P 3 3

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

Yes
3
2 4 1 

Примечание

Заметьте, что мы не отличаем начало провода от конца, т.е. мы можем менять начало и конец провода (не всей цепи!) местами.