VK очень часто проводит хакатоны, где программисты решают разные задачи. Сейчас VK готовит новый хакатон, в котором все желающие могут попробовать себя в разработке уникального полезного приложения или сервиса для одного из нескольких треков, в числе которых Финтех, Культура, Медиа и другие.

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

В этот раз VK организует новый хакатон, и на него на площадке проведения собрались $$$m$$$ участников. Для этих $$$m$$$ участников организаторы заказали $$$n$$$ пицц, которые на площадке расположили в ряд и пронумеровали от $$$1$$$ до $$$n$$$. Известно, что

• каждая пицца состоит из бесконечного числа кусочков;
• первый кусочек $$$i$$$-й пиццы имеет толщину теста $$$a_i$$$, а каждый следующий — на $$$1$$$ больше предыдущего (то есть $$$a_i + 1$$$, $$$a_i + 2$$$, и так далее);
• наиболее привлекательными для участников кажутся кусочки с наименьшей толщиной теста;
• любой участник может подойти к ряду с пиццами в произвольном месте, но после может перемещаться только влево (в сторону меньших номеров), чтобы не мешать другими участникам.

Периодически участники встают со своих мест и подходят к ряду пицц, чтобы взять один кусочек. Участник номер $$$i$$$ подходит к пицце с номером $$$s_i$$$ в момент времени $$$t_i$$$, после чего моментально находит кусочек пиццы с наименьшей толщиной теста среди пицц от $$$1$$$-й до $$$s_i$$$-й и начинает двигаться в его сторону. На перемещение между двумя соседними пиццами у каждого участника уходит одинаковое время — $$$v$$$ секунд. Несколько участников могут одновременно находиться около одной пиццы.

Как только участник подходит к пицце, кусочек в которой он выбрал, он его забирает и уходит обратно на свое место. Если несколько участников выбрали один и тот же кусочек и подошли к нему одновременно, кусочек забирает участник с меньшим номером. При этом если кусочек, на который рассчитывал участник, кто-то забрал, этот участник моментально выбирает новую цель по тому же алгоритму: он смотрит на все пиццы от первой до его текущей позиции, выбирает среди них минимум, и начинает двигаться к нему.

Формально этот процесс можно описать следующим образом. В каждое целое число секунд $$$t$$$:

1. все участники, уже стоявшие в ряду в момент времени $$$t - 1$$$, сдвигаются на $$$\frac{1}{v}$$$ влево;
2. все участники с $$$t_i = t$$$ подходят к пицце с номером $$$s_i$$$;
3. время «останавливается»;
4. определяются все участники, стоящие на таких целых позициях $$$p$$$, что $$$a_p = \min(a_1, a_2, \ldots, a_p)$$$;
5. для каждого такого $$$p$$$ участник с минимальным номером, стоящий на позиции $$$p$$$, забирает кусочек пиццы толщиной $$$a_p$$$ и уходит; $$$a_p$$$ увеличивается на $$$1$$$;
6. после того, как некоторые кусочки пицц забрали, могло случиться так, что у каких-то участников изменилась минимальная толщина кусочка, который они все еще могут получить, в таком случае процесс повторяется с шага 4;
7. иначе, время «запускается заново» и процесс переходит на следующую секунду.

По информации о подходах участников к пиццам определите для каждого участника, кусочек пиццы какой толщины ему достался и сколько времени он провел в ряду.

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