Недавно Миша и Филипп заполучили власть над температурой воздуха в своих любимых городах — Липецке и Москве. Сейчас температура воздуха в Липецке — $$$x$$$ градусов, а температура воздуха в Москве — $$$y$$$ градусов. Они планируют играть в свою любимую игру, которая называется «Уравняй».

Суть игры заключается в следующем. Сначала Миша уменьшает температуру в Липецке на $$$a$$$ и увеличивает температуру в Москве на $$$a$$$. Затем Филипп уменьшает температуру в Москве на $$$b$$$ и увеличивает температуру в Липецке на $$$b$$$. Если температура в двух городах стала равной, то друзья радуются и идут спать. В противном случае, Миша снова меняет температуру в обоих городах описанным способом, а затем Филипп меняет температуру в обоих городах описанным образом. Друзья будут выполнять данные действия до тех пор, пока температура воздуха в Липецке и Москве не станет одинаковой. Обратите внимание, что Миша и Филипп должны сделать одинаковое количество операций изменения температуры.

Так как они не хотят всю жизнь играть в данную игру, вам придется им подсказать, сравняется ли в какой-то момент температура воздуха в Липецке и Москве. При этом, если это произойдет, то вам нужно сказать, сколько пар изменений произойдет для достижения этого великого события.

Помимо примеров из условия данная задача содержит $$$25$$$ тестов, каждый из которых оценивается независимо в $$$4$$$ балла.

Решения, правильно работающие при $$$1 \le x, y, a, b \le 100\,000$$$, будут оцениваться не менее, чем $$$40$$$ баллами.

Недавно Даниил участвовал в командной олимпиаде. В почетном дипломе третьей степени он обнаружил массив $$$a$$$, состоящий из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$, а также число $$$k$$$.

После этого он решил поиграть с обнаруженным массивом. Для этого мальчик $$$q$$$ раз изменяет некоторый элемент массива. Каждое изменение характеризуется двумя числами $$$x$$$ и $$$y$$$, которые означают, что Даниил заменяет элемент массива на позиции $$$x$$$ (который раньше был равен $$$a_x$$$) на число $$$y$$$.

После каждого изменения Даниил хочет посчитать количество таких пар $$$(l, r)$$$, что $$$1 \le l \lt r \le n$$$ и сумма $$$(a_l + a_r)$$$ делится на $$$k$$$ без остатка. Сейчас мальчик празднует по поводу получения диплома, поэтому не способен решить эту задачу сам.

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

Зачем горилла Коко прыгала по лианам? Оказывается, что у нее была вполне конкретная цель: Коко спешила на обед.

Обед гориллы организован следующим образом. В начале ей выдают поднос, на котором разложены $$$n$$$ фруктов, пронумерованных числами от $$$1$$$ до $$$n$$$. Если горилла съест $$$i$$$-й фрукт, она получит $$$a_i$$$ единиц удовольствия от еды. Коко может сама выбирать, какие фрукты съесть, а какие проигнорировать. После того, как горилла съела все фрукты, которые захотела, поднос уносят, а вместо него приносят точно такой же поднос, на котором снова разложены $$$n$$$ фруктов. Затем Коко снова съедает те фрукты, которые захочет, после чего поднос уносят, и процесс продолжается аналогично.

Однако, все не так просто: горилла Коко очень любит разнообразие. Поэтому если в какой-то момент она съест $$$i$$$-й фрукт, принесенный ей на подносе, то в следующий раз, когда горилла захочет снова съесть $$$i$$$-й фрукт, он принесет ей на $$$b_i$$$ единиц удовольствия меньше, чем в предыдущий раз. Иными словами, когда горилла впервые съедает $$$i$$$-й фрукт, она получает $$$a_i$$$ единиц удовольствия. Когда Коко съедает $$$i$$$-й фрукт во второй раз, она получает $$$a_i - b_i$$$ единиц удовольствия. Когда она захочет съесть $$$i$$$-й фрукт в третий раз, то количество единиц полученного удовольствия будет равняться $$$a_i - 2 \cdot b_i$$$, и так далее. Обратите внимание, что некоторые съеденные фрукты могут приносить горилле отрицательное количество единиц удовольствия, однако есть такие фрукты тоже можно.

Горилла Коко знает, что за сегодняшний день поднос с едой будет принесен ровно $$$k$$$ раз. Также она решила, что хочет съесть ровно $$$t$$$ фруктов за весь день (имеется ввиду именно суммарное количество фруктов с учетом того, что некоторые фрукты Коко может съесть несколько раз). Разумеется, Коко хочет, чтобы суммарное количество единиц удовольствия, полученных ей от всех съеденных фруктов, было как можно больше.

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

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

Вася готовится к заключительному этапу ВсОШ по информатике. По его плану за $$$n$$$ оставшихся дней до олимпиады он должен решить хотя бы $$$x$$$ задач.

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

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

Для лучшего понимания рассмотрим следующий пример. Пусть до олимпиады осталось пять дней, и Вася планирует решить хотя бы $$$15$$$ задач, решая каждый день не более, чем четыре задачи. Тогда один из вариантов тренировок выглядит следующим образом. В первый день Вася решит четыре задачи, во второй день — на одну задачу меньше, то есть три задачи. В третий день Вася решит две задачи. В четвертый день вы будете решать контест вместе с Васей, поэтому он решит четыре задачи. В пятый день Вася решит три задачи. Таким образом, суммарно за пять дней Вася решит $$$4 + 3 + 2 + 4 + 3 = 16$$$ задач.

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

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

Как известно, Кирилл — восходящий спортсмен. Он соблюдает диету, никогда не пропускает тренировки, а также ежедневно бегает по утрам на стадионе около своего дома.

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

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

Для лучшего понимания процесса рассмотрим следующий пример: пусть вдоль стадиона посажены шесть деревьев следующих типов: $$$1, 3, 2, 3, 2, 2$$$, а $$$k = 4$$$. Кирилл начинает пробежку и фотографирует первые $$$k$$$ деревьев, которые имеют типы $$$1$$$, $$$3$$$, $$$2$$$ и $$$3$$$. После этого Кирилл останавливается и отправляет тренеру одну фотографию дерева типа $$$1$$$, одну фотографию дерева типа $$$2$$$, и одну фотографию дерева типа $$$3$$$. После чего он очищает память телефона, становится напротив дерева с номером $$$5$$$ и продолжает пробежку. Далее Кирилл сфотографирует деревья типов $$$2$$$, $$$2$$$, $$$1$$$ и $$$3$$$, отправит тренеру по одной фотографии каждого из деревьев первого, второго, и третьего типов. Далее Кирилл пробежит вдоль деревьев с типами $$$2$$$, $$$3$$$, $$$2$$$ и $$$2$$$, и отправит тренеру одно фото дерева типа $$$2$$$ и одно фото дерева типа $$$3$$$. После этого Кирилл поймет, что следующее дерево имеет номер $$$1$$$, и пойдет домой.

Таким образом, Кирилл отправит тренеру две фотографии деревьев первого типа, три фотографии деревьев второго типа и три фотографии деревьев третьего типа.

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

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