Известный завод ждет реорганизация — его собираются переоборудовать 𝑛 новейшими станками. Перед тем, как эти станки будут установлены, требуется разработать интерфейс для обработки задач на этих станках.
После реорганизации наладчик завода будет распределять поступающие задачи между станками. У каждой задачи есть длительность. У каждого станка есть независимая очередь задач, причем новую задачу можно добавить либо строго в конец этой очереди, либо строго в начало, если это срочная задача.
Станки работают строго в порядке очереди, обрабатывая задачи подряд. Как только станок завершает задачу, он сразу же начинает работу над следующей в очереди, если такая есть. На переключение между задачами время не тратится.
Формально определим время начала работы над задачей как первый момент времени, после которого прогресс по задаче строго увеличится. Так, если в момент времени 𝑡 на свободный станок приходят сначала обычная задача 𝐴 и затем срочная задача 𝑈, временем начала 𝑈 станет 𝑡, а временем начала 𝐴 — момент завершения 𝑈.
Аналогично, время завершения работы над задачей — первый момент времени, когда прогресс по задаче достигает ее длительности. Так, если в момент времени 𝑡 прогресс по задаче 𝐴 достиг ее длительности, и станку поступил запрос на обработку срочной задачи 𝑈, временем завершения 𝐴 все равно будет 𝑡.
Для большего понимания советуем после прочтения условия ознакомиться с иллюстрацией внизу.
Всего поддерживается четыре типа запросов.
- Добавить задачу номер 𝑖 длительностью 𝑑 в конец очереди 𝑘-го станка.
Если его очередь до этого была пустой, станок тут же начинает работу над добавленной задачей
- Отменить задачу с номером 𝑖. Если эта задача еще не была начата, она удаляется из очереди, а порядок остальных задач в очереди не меняется. Если эта задача уже была начата, работа над ней тут же останавливается, и станок берет в работу следующую задачу из очереди. Если эта задача уже была завершена или такой задачи не было, запрос отмены игнорируется
- Добавить срочную задачу с номером 𝑖 длительностью 𝑑 в начало очереди 𝑘-го станка. В этом случае работа над текущей задачей (если она есть) на 𝑘 -м станке приостанавливается с сохранением прогресса, и в работу берется данная срочная задача.
До момента завершения срочной задачи все запросы добавления или отмены новых задач к станку номер 𝑘 игнорируются для экономии ресурсов. Иными словами, если в момент времени 𝑡 поступил запрос добавления срочной задачи, все следующие запросы, поступающие к 𝑘-му станку в моменты времени с 𝑡 включительно до 𝑡 + 𝑑 не включительно будут проигнорированы.
По завершении срочной задачи, если работа над какой-то обычной задачей в очереди была приостановлена, эта задача без задержек возвращается в обработку.
- Вывести ожидаемый момент времени завершения работы 𝑘-го станка.
Для станка без задач в очереди «ожидаемым» временем завершения его работы будем считать текущий момент времени.
Еще раз обратите внимание, что во время исполнения срочной задачи станок игнорирует только все запросы добавления и отмены задач (включая добавление другой срочной задачи). Про запрос отмены будем считать, что он идет к тому станку, в очереди которого лежит соответствующая задача. Запросы вывода ожидаемого момента завершения работы не игнорируются.
Вам необходимо помочь наладчику и вывести для каждой задачи время начала и завершения работы над ней.
Формат входных данных
В первой строке дано целое число 𝑇 (1 ≤ 𝑇 ≤ 1000) — количество наборов входных данных. В первой строке описания набора входных данных через пробел даны два целых числа 𝑛 и 𝑞 (1 ≤ 𝑛, 𝑞 ≤ 10
5) —
количество станков и количество запросов. Гарантируется, что сумма 𝑛 и сумма 𝑞 по всем наборам входных данных обе не превосходят 10
5.
В следующих 𝑞 строках описаны запросы к заводу в одном из следующих форматов:
1. «𝑡 𝑠𝑐ℎ𝑒𝑑𝑢𝑙𝑒 𝑖 (𝑑) 𝑜𝑛 𝑘» — добавить задачу на 𝑘-й станок;
2. «𝑡 𝑐𝑎𝑛𝑐𝑒𝑙 𝑖» — отменить задачу;
3. «𝑡 𝑢𝑟𝑔𝑒𝑛𝑡 𝑖 (𝑑) 𝑜𝑛 𝑘» — добавить срочную задачу на 𝑘-м станке;
4. «𝑡 𝑒𝑥𝑝𝑒𝑐𝑡𝑎𝑡𝑖𝑜𝑛 𝑘» — узнать текущее ожидаемое время завершения работы 𝑘-го станка.
Параметр 𝑡 — момент совершения запроса (целое неотрицательное число от 0 до 10
9). Для всех запросов выполняется 1 ≤ 𝑘 ≤ 𝑛, 1 ≤ 𝑖 ≤ 109 и 1 ≤ 𝑑 ≤ 10
9.
Также гарантируется, что номера задач (𝑖) уникальны и не повторяются, а запросы упорядочены по времени, то есть 𝑡 каждого следующего запроса не меньше, чем 𝑡 предыдущего.
Формат выходных данных
Выведите в отдельной строке текущее ожидаемое время работы соответствующего станка после каждого запроса типа «𝑒𝑥𝑝𝑒𝑐𝑡𝑎𝑡𝑖𝑜𝑛».
Затем выведите по строке на каждую задачу, запрос на добавление которой не был проигнорирован. Задачи должны быть упорядочены по возрастанию их номеров. В каждой строке через пробел должны быть выведены три числа: номер задачи, время начала ее обработки и время конца ее обработки (или отмены, если задача была отменена до завершения).
Для задач, которые были отменены до начала работы над ними, считайте время начала равным времени первого запроса их отмены.
Замечание
В первом примере из условия обе задачи будут обработаны по расписанию: с 0 до 10 и с 4 до 7 соответственно.
Во втором примере:
1. первая задача должна обрабатываться на первом станке в период [0, 5];
2. вторая задача должна обрабатываться на втором станке в период [0, 5];
3. в момент времени 2 срочная задача номер 3 добавляется на первый станок; она будет обрабатываться в период [2, 7];
4. в момент времени 6 первому станку нужно еще 4 единицы времени на завершение задач 4 и 1; второй станок завершил работу в момент времени 5, а третий станок вообще не начинал работу — для них время ожидания до завершения работы равно 0.
Подробная иллюстрация к третьему примеру приведена ниже. Здесь синим обозначен прогресс по задачам, зеленым — завершенные задачи, красным — отмененные, а градиентом — срочные. Все интервалы короче 1 единицы времени (см. отмененную задачу 3) стоит воспринимать как интервалы длительностью 0.
