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

Электронное письмо можно упрощённо представить в виде структуры


struct Message {
int userId; // id получателя
string from; // email-адрес отправителя
unsigned receiveTimestamp; // время получения
int folderId; // id папки, в которую доставлено письмо
int threadId; // id цепочки (треда), в которую группируются письма при обсуждении
};

Нужно реализовать хранилище писем, в которое можно складывать письма и у которого можно запрашивать список писем по параметрам. Параметрами для запроса являются:

  1. id юзера $$$userId$$$
  2. id папки $$$folderId$$$
  3. отрезок времени получения письма $$$[since, till]$$$, включительно
  4. максимальное количество элементов в выдаче $$$count$$$

Письма в выдаче должны быть сгруппированы в треды (сначала идут письма первого треда, затем второго и так далее). Таймстемпом треда считается таймстемп самого свежего письма в этом треде.

Должны выбираться только треды, принадлежащие папке $$$folderId$$$. Считается, что тред принадлежит папке $$$folderId$$$, если хотя бы одно письмо из этого треда лежит в папке $$$folderId$$$. Таким образом в выдаче писем могут присутствовать письма с $$$folderId$$$, отличающимся от переданного.

В выдачу должны попасть только треды, таймстемпы которых попадают в отрезок $$$[since, till]$$$, включительно.

Треды в выдаче должны быть отсортированы по убыванию своих таймстемпов. Для тредов с одинаковым таймстемпом сортировка идет по увеличению $$$threadId$$$. Письма внутри треда должны быть отсортированы по убыванию таймстемпа. Для писем с одинаковым таймстемпом сортировка идет по порядку сохранения в хранилище.

После всех группировок применяется правило для ограничения количества элементов в выдаче: надо выбрать $$$count$$$ первых.

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

На вход программе подается последовательность строк вида


n q
+ <userId> <from> <timestamp> <folderId> <threadId>
...
? <userId> <folderId> <since> <till> <count>
...
  1. Первая строка содержит два целых числа $$$n$$$ (количество запросов на добавление письма, $$$0 \le n \le 10^5$$$ ) и $$$q$$$ (кол-во запросов на выборку писем, $$$0 \le q \le 10^4$$$)
  2. после первой строки идет $$$n+q$$$ запросов: $$$+$$$ (действие "сложить письмо") или $$$?$$$ (действие "получить выдачу"), действия могут чередоваться
  3. $$$userId$$$, $$$folderId$$$, $$$threadId$$$ - произвольные целые числа, $$$0 \le userId \le 10^5$$$, $$$0 \le folderId \le 10^2$$$, $$$0 \le threadId \le 10^5$$$
  4. $$$timestamp$$$, $$$since$$$, $$$till$$$ - произвольные целые числа в отрезке $$$[0, 10^9]$$$, причем $$$since \le till$$$
  5. $$$0 \le count \le 10^2$$$
  6. $$$from$$$ - строка из символов $$$[a-z0-9@.]$$$, длиной $$$M$$$, где $$$1 \le M \le 256$$$
Выходные данные

Программа должна для каждой операции $$$?$$$ выдать следующую секцию:


M
<userId> <from> <timestamp> <folderId> <threadId>
...
<userId> <from> <timestamp> <folderId> <threadId>

где $$$M$$$ - количество элементов в выдаче на запрос $$$?$$$. После строки с числом $$$M$$$ следует столько же строк, каждое обозначает письмо. Количество таких секций равняется количеству действий $$$?$$$ во входном файле.

Примеры
Входные данные
8 1
+ 0 [email protected] 39 0 0
+ 0 [email protected] 83 0 0
+ 0 [email protected] 91 1 0
+ 0 [email protected] 0 1 0
+ 1 [email protected] 61 0 0
+ 1 [email protected] 64 0 0
+ 1 [email protected] 89 1 0
+ 1 [email protected] 45 1 0
? 1 0 3 90 2
Выходные данные
2
1 [email protected] 89 1 0
1 [email protected] 64 0 0
Входные данные
2 1
+ 1 [email protected] 1 1 1
+ 1 [email protected] 2 1 2
? 1 1 0 10 1
Выходные данные
1
1 [email protected] 2 1 2