Быть преподавателем — тяжкий неблагодарный труд. Сначала студенты весь семестр прогуливают твои пары, предпочитая им теплую мягкую постель (хотя бы предупреждали, что не придут, не только им ведь хочется спать!), а потом приходится выслушивать их несуразные ответы на зачете. Устав от этого безобразия, почтенный профессор придумал новый способ принятия зачета.
За каждым человеком из группы, в которой учится n2 студентов, закрепляется клеточка на квадратном поле, в которой стоит «Не зачтено». Ничего не подозревающий староста называет произвольное число k, и начинается самое интересное. Профессор выбирает произвольную строку или столбец и меняет там все отметки на противоположные. Такую операцию он проделывает до тех пор, пока ровно у k студентов не будет стоять «Зачтено». После этого зачет завершается и k счастливчиков отправляются праздновать успешное завершение сессии. Однако бывают случаи, когда по системе профессора невозможно получить k зачетов на бланке. Тогда на пересдачу отправляется вся группа. Отличник должен помочь старосте и ответить, получат ли несколько счастливцев сегодня зачет, если тот назовет число k.
В первой строке задаются два целых числа n и t — размер поля, закрепленного за студентами, и количество тестов. В следующей строке задаются числа q0 a b m. Эти числа используются старостой для генерации t возможных чисел ki согласно следующему правилу:
Выведите количество чисел среди ki (1 ≤ i ≤ t) для которых возможно выбрать счастливчиков, которые получат зачет.
5 6
9 1 2 999999993
4
85 155
88 120 53 980090303
42
