Информатика

Автобусные остановки расположены через каждые K метров от начала улицы, то есть на расстоянии 0, K, 2K, 3K и т.д. метров от начала. Света прошла от начала улицы N метров, после чего
устала и захотела сесть на автобус. Определите, сколько метров нужно пройти Свете до ближайшей
остановки.

Входные данные
Программа получает на вход два целых числа K и N, записанных в отдельных строках.
1 ≤ K ≤ 2 × 10⁹, 1 ≤ N ≤ 2 × 10⁹

Выходные данные
Программа должна вывести одно целое число — расстояние до ближайшей остановки.
 

Примеры

№	Входные данные	Выходные данные
1	600 2000	200

Правильный способ определения конструктора данного класса при создании объектов классов:

   maths s1 = new maths();
   maths s2 = new maths(5, 5.4f);

A)

  public maths(int pp, single tt)
   {
       p = pp;
       t = tt;
   }

B) sample s;
C)

 public sample()
   {
      p = 0;
      t = 0.0f;
   }
  public sample(int pp, single tt)
  {
       p = pp;
       t = tt;
  }

D) s = new sample();

Количество конструкторов, которые может определить класс, равно?
A) 1
B) 2
C) Любое число
D) Ни один из упомянутых

Выберите неверное утвеждение:

1) Возможно инициализировать нестатические поля данных в статическом конструкторе.
2) Можно инициализировать статические поля данных в нестатическом конструкторе, но после этого они теряют свой статический характер.
3) Можно инициализировать статические поля данных как в статических, так и в нестатических конструкторах, но статические поля данных теряют свой статический характер.
4) Возможно инициализировать нестатические поля данных в нестатическом конструкторе.

Какое из следующих утверждений о конструкторах верно?

1. Если мы предоставляем конструктор с одним аргументом, то компилятор по-прежнему предоставляет конструктор без аргументов.
2. Статические конструкторы могут использовать необязательные аргументы.
3. Перегруженные конструкторы не могут использовать необязательные аргументы.
4. Если мы не предоставляем конструктор, компилятор предоставляет конструктор без аргументов.

Какое из следующих утверждений верно?

A. Конструктор может использоваться для установки значений по умолчанию.
B. C# обеспечивает конструктор копирования.
C. Деструкторы используются как с классами, так и со структурами.
D. Класс может иметь более одного деструктора.

Вожди известного племени Мумба-Юмба решили придумать новый боевой вопль для своих воинов. При этом они решили, что вопль должен состоять ровно из N букв (всего в алфавите племени M букв). Также, после долгих исследований было выяснено, что если в вопле встречается слово s_i  (слово – это последовательность букв алфавита, не длиннее трех символов), то этот вопль вселяет во врага f_i единиц страха. Если в вопль входит несколько слов, то их “страшность” суммируется. Например, если вопль содержит слова s_i и s_j, то вопль вселяет f_i+f_j единиц страха. 
Требуется по заданным N, M, алфавиту и списку слов s_i составить максимально страшный вопль. 

Входные данные:
В первой строке записано три числа – N, M и К (0<N≤100, 0<M<25, 0 ≤ K ≤ 100), где K – количество страшных слов. В следующей строке записан алфавит – строка из M строчных латинских букв. Далее в K строках записана информация о словах – само слово и через пробел одно число, обозначающее страшность этого слова (0 < f_i ≤ 10000).

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

Примеры

№	Входные данные	Выходные данные
1	3 5 4 abcde abc 10 ab 5 be 7 e 4	16 abe

Однажды злой волшебник Сарумян поглядел в видеочат и узрел там систему из N зеркал. Долго думал он, прежде чем внутренний голос подсказал ему, что система не простая. Он понял, что если посмотреть на эту систему под некоторым углом, и увидеть заданную точку А через все N зеркал (то есть так, чтобы его взгляд отразился через каждое из них ровно по одному разу, а потом попал в точку A), то откроются ему все тайны интернета. 
Однако светлые силы не дремали и через агентурную сеть выяснили все про этот видеочат. 
Требуется написать программу, которая подсказала бы светлым силам, под каким углом нужно посмотреть на систему зеркал, чтобы узнать все тайны интернета.

Входные данные:
В первой строке входного файла записано одно число – количество зеркал (0<N≤10). В следующей строке записаны координаты (x и y, где ось x направлена вправо, ось y – вверх) исходной точки (откуда надо смотреть на зеркала) и точки A. Далее в N строках записана информация о зеркалах – по четыре числа, обозначающие координаты начала и конца зеркала. Отражающая поверхность расположена на левой стороне зеркала (если смотреть от первой точки в направлении второй). С обратной стороны зеркала прозрачны.
Причем выполняются следующие ограничения:
•    Все координаты вещественны и по модулю не превосходят 10000
•    Никакие зеркала не пересекаются 
•    Конечная и начальная точки не лежат ни на одном из зеркал

Выходные данные:
В первую строку выходного файла необходимо записать YES, если решение существует, и NO, если нет. Если решение есть, то во вторую строку надо записать угол в градусах (с точностью до шести знаков после запятой), под которым нужно смотреть на зеркала. Угол отсчитывается против часовой стрелки от оси Ox и лежит в пределах от 0 до 360 градусов.

Примеры

№	Входные данные	Выходные данные
1	2  0 0 0 5 1 0 1 2 -1 4 –1 2	YES 51.340192

Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований ученые пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Если бы этот вывод оказался верным, это доказало бы не только то, что на Марсе много лет назад были разумные существа, но и то, что они уже умели считать…
Ученые смогли понять, что в этом случае означают найденные символы, и перевели эти равенства на обычный язык — язык цифр, скобок, знаков арифметических действий и равенства. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции — сложение, умножение и вычитание (марсиане никогда не использовали “унарный минус”: вместо “–5” они писали “0–5”). Также ученые доказали, что марсиане не наделяли операции разным приоритетом, а просто вычисляли выражения (если в них не было скобок) слева направо: например, 3 + 3*5 у них равнялось 30, а не 18.
К сожалению, символы арифметических действий марсиане почему-то наносили специальными чернилами, которые, как оказалось, были не очень стойкими, и поэтому в найденных листках между числами вместо знаков действий были пробелы. Если вся вышеизложенная теория верна, то вместо этих пробелов можно поставить знаки сложения, вычитания и умножения так, чтобы равенства стали верными. Например, если был найден лист бумаги с надписью “18=7 (5 3) 2”, то возможна такая расстановка знаков: “18=7+(5–3)*2” (помните про то, в каком порядке марсиане вычисляют выражения!). В то же время, если попался лист с надписью “5=3 3”, то марсиане явно не имели в виду числового равенства, когда писали это…
Вы должны написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует.

Формат входных данных
Первая строка входного файла состоит из натурального (целого положительного) числа, не превосходящего 2³⁰, знака равенства, и последовательности натуральных чисел (не более десяти), произведение которых также не превосходит 2³⁰. Некоторые группы чисел (одно или более) могут быть окружены скобками. Длина входной строки не будет превосходить 80 символов, и других ограничений на количество и вложенность скобок нет. Между двумя соседними числами, не разделенными скобками, всегда будет хотя бы один пробел, во всех остальных местах может быть любое (в том числе и 0) число пробелов (естественно, внутри числа пробелов нет).

Формат выходных данных
В выходной файл необходимо вывести одну строку, содержащую полученное равенство (т.е., исходное равенство со вставленными знаками арифметических действий). В случае если требуемая расстановка знаков невозможна, вывести строку, состоящую из единственного числа “–1”. Выходная строка не должна содержать пробелов.
 

Примеры

№	Входные данные	Выходные данные
1	18=7 (5 3) 2	18=7+(5–3)*2
2	5= 3 3	-1

Для того чтобы проверить, как ее ученики умеют считать, Мария Ивановна каждый год задает им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A.
Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.
Формат входных данных
Во входном файле содержится единственное число A (1 ≤ A ≤ 1000000000 — на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы кого-нибудь “завалить”).
Формат выходных данных
В выходной файл выведите единственное число N.
 

Примеры

№	Входные данные	Выходные данные
1	8	4
2	13	13

Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: «Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под ним». Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений (1 – север, 2 – северо-восток, 3 – восток, 4 – юго-восток, 5 – юг, 6 – юго-запад, 7 – запад, 8 – северо-запад) (см. рис). Длина шага в любом направлении равна 1.
    Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис).


Вам необходимо написать программу, которая по указаниям пиратов определяет точку, где зарыт клад.
 Формат входных данных
    Первая строка  содержит число N – число указаний (1≤N≤40). Последующие N строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.
Формат выходных данных
    Выведите координаты X и Y точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось Ox направлена на восток, а ось Oy – на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с погрешностью не более 10^-3.
 

Примеры

№	Входные данные	Выходные данные
1	6 1 3 3 1 1 1 3 3 5 2 7 1	3.000 2.000
2	1 8 10	-7.071 7.071

Ильдар и Ваня устали постоянно играть в шахматы, поэтому они придумали новую шахматную игру.

Игра происходит на шахматном поле размером 2n×2m. Это поле имеет 2n строк и 2m столбцов. Для удобства будем обозначать как (i, j) клетку поля, которая находится в i-й строке и j-м столбце. Клетки этого поля покрашены в черный и белый цвета шахматной раскраской. Более точно, клетка (i, j) имеет белый цвет, если i + j чётно, и чёрный цвет в противном случае.

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

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

Помогите Ильдару сделать игру интересной! Напишите программу, которая будет отвечать на его запросы.

Формат входных данных
В первой строке находится три целых числа n, m, q (1 ≤ n, m, q ≤ 200 000) — количество пар строк шахматной доски, количество пар столбцов шахматной доски и количество запросов. 
Следующие q строк описывают запросы Ильдара. Каждая из этих строк содержит два целых числа i, j (1 ≤ i ≤ 2n, 1 ≤ j ≤ 2m, i+j четно). Если клетка (i, j) не вырезана, то Ильдар её вырезает, иначе он возвращает её обратно на поле.

Формат выходных данных
Выведите q строк. В i-й из этих строк выведите ответ на задачу для доски, полученной после i первых запросов Ильдара.
Выведите «YES» (без кавычек), если Ваня может так расставить шахматных королей на не вырезанные белые клетки поля, что никакие два короля не будут бить друг друга. Иначе выведете «NO» (без кавычек).
 

Примеры

№	Входные данные	Выходные данные
1	1 3 3 1 1 1 5 2 4	YES YES NO
2	3 2 10 4 2 6 4 1 3 4 2 6 4 2 2 2 4 1 3 4 4 3 1	YES YES NO NO YES YES NO YES YES NO

Замечание
В первом примере, после второго запроса будут вырезаны клетки (1, 1) и (1, 5). Тогда Ваня может поставить три короля на клетки (2, 2), (2, 4) и (2, 6).
После третьего запроса будут вырезаны клетки (1, 1), (1, 5) и (2, 4). Тогда остаётся всего три пустые клетки (2, 2), (1, 3) и (2, 6). Ваня не может поставить трех королей на эти клетки, потому что короли в клетках (2, 2) и (1, 3) бьют друг друга, так как эти клетки соседние по углу.
 

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

Изначально, до появления Байтландии, на её территории были расположены n различных стран. Каждое государство владело своей территорией, которую можно было представить на карте как прямоугольник, стороны которого параллельны осям координат, а вершины расположены в целочисленных точках. Никакие две страны не пересекались, однако они могли касаться сторонами. Иногда в результате агрессивных переговоров и мирных военных походов две страны объединялись в одну. Слияние происходило только в том случае, если после объединения их владений снова получалась прямоугольная территория. В конце концов осталось только одно государство — Байтландия.

В начале времён территория каждой страны содержала внутри себя ровно один прямоугольный замок, где стороны этого замка параллельны осям координат, а вершины расположены в целочисленных точках. Допускается, что границы замка могли прилегать к границе соответствующей территории страны и к границам других замков. Удивительным образом, даже после всех переворотов, замки прекрасно сохранились. Но, к сожалению, это единственная информация, которая позволяет хоть как-то судить об изначальном расположении стран.
  Петя не смог смириться с тем, что не осталось никаких данных об изначальных странах. У него возникло подозрение, что вся эта история всего лишь вымысел. Он знает, что вы умный человек, и поэтому просит у вас помощи. Требуется выяснить, существует ли расположение изначальных государств, для которых может быть верна данная история, или нет.

Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 100000) — количество замков и стран.

Каждая из следующих n строк содержат четыре целых числа a_i, b_i, c_i, d_i (0 ≤ a_i  < c_i ≤ 10⁹, 0 ≤ b_i < d_i ≤ 10⁹) — координаты вершин i-го замка, где (a_i, b_i) — координаты левой нижней точки, а (c_i, d_i) — правой верхней.

Гарантируется, что никакие два замка не пересекаются, однако они могут касаться сторонами.

Выходные данные
Если существуют расположения изначальных стран, для которых верна данная история, то выведите « YES », иначе выведите « NO ».

Примечание
На картинках ниже изображено расположение замков в первом и втором примере.

Примеры

№	Входные данные	Выходные данные
1	4 0 0 1 2 0 2 1 3 1 0 2 1 1 1 2 3	YES
2	4 0 0 2 1 1 2 3 3 2 0 3 2 0 1 1 3	NO

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

Каждый день на планете Кирнес состоит из h часов. Каждый час состоит из m минут, причём m обязательно чётное. Известно, что на данный момент n товарных поездов отправляются с вокзала ежедневно по разу в день: i-й поезд отправляется в h_i часов и m_i минут.

Поскольку между Кирнесом и Сириусом активный пассажиропоток, то было решено пустить ровно по 2 электрички каждый час. Более того, по всем транспортным нормам необходимо, чтобы промежутки времени между отправлением электричек были равны \( {m \over 2}\)минутам. То есть для любой электрички предыдущая должна была отправиться ровно за \({m \over 2}\) минут до неё, а следующая должна отправиться ровно через \({m \over 2}\) минут после. Кроме этого, электричку надо подать на платформу за k минут до отправки. Пока электричка стоит на платформе, с неё не могут отправляться товарные поезда. При этом разрешается подавать электричку на платформу в ту же самую минуту, когда с неё отправляется предыдущий товарный поезд. А также поезда отправляются настолько быстро, что разрешено отправить электричку и следующий за ней товарный поезд в одну и ту же минуту.

Поскольку электрички отправляются каждый день с интервалом в \({m \over 2}\) минут, то первая электричка отправится с вокзала в 0 часов и t минут, причем t < \({m \over 2}\) . Обратите внимание, что если t < k, то платформа вокзала будет занята и последние k − t минут предыдущего дня.

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

Составление такого расписания оказалось трудной задачей для правительства планеты, поэтому это было поручено вам. Найдите такое время t для запуска первой электрички, чтобы количество товарных поездов, которые потребуется отменить, было минимальным.

Формат входных данных
Первая строка содержит четыре целых числа n, h, m, k (1 ≤ n ≤ 100 000, 1 ≤ h ≤ 10⁹, 2 ≤ m ≤ 10⁹, 1 ≤ k ≤ \({m \over 2}\)) — число товарных поездов, количество часов и минут на планете Кирнес, а также время, которое электричка стоит у платформы. Гарантируется, что число минут m четное.
В следующих n строках вводится по два целых числа hi и mi (0 ≤ h_i < h, 0 ≤ m_i < m) — время отправления i-го поезда, часы и минуты соответственно. Гарантируется, что все товарные поезда отправляются в разное время.

Формат выходных данных
Выведите два числа: минимальное количество отмененных товарных поездов и t — время запуска первой за день электрички в минутах.
Во второй строке через пробел выведите номера отменяемых товарных поездов.

Примеры

№	Входные данные	Выходные данные
1	2 24 60 15 16 0 17 15	0 0
2	2 24 60 16 16 0 17 15	1 0 2

Замечание

В первом примере первую электричку надо отправить в 0:00. Тогда поезд в 16:00 отправится сразу после электрички, а электричку в 17:30 надо будет подать на платформу сразу после отправления товарного поезда в 17:15.
Во втором примере подать электричку на платформу надо за 16 минут до отправления. Сделать это без отмены какого-то товарного поезда не получится: если отправлять электричку в t ∈ [1, 15], то в 16:00 электричка уже должна быть на платформе, а с нее в это время отправляется первый товарный поезд. Если t ∈ {0, [16, 29]}, то второй товарный поезд в 17:15 не сможет уехать с платформы, потому что на ней уже будет стоять следующая электричка.
Если отменить второй поезд, то можно выбрать t = 0, тогда поезда будут отправляться в 0 и 30 минут каждый час, а столкновения с первым товарным поездом не будет. Также можно отменить только первый поезд и выбрать, например, t = 13.
 

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

Как известно, любому таланту надо дать возможность реализоваться, поэтому мама Миши отправила сына на инновационную олимпиаду по ирригации (ИОИ). На этой олимпиаде школьники со всех концов Берляндии соревнуются в умении доставить воду для поливки растений самыми причудливыми способами. Зная список изобретений Миши, несложно догадаться, что проведение подобной олимпиады весьма затратно, поэтому спустя n первых проведений олимпиады было решено ввести правило, по которому будет определяться место проведения соревнования в следующий год. Город для проведения олимпиады выбирается следующим образом: всего в Берляндии есть m городов, пронумерованных от 1 до m, готовых принять соревнование. Каждый год олимпиада проводится в городе, в котором она проводилась наименьшее число раз. Если таких городов несколько, то олимпиада проводится в городе с наименьшим номером среди городов с минимальным числом проведений олимпиады.

Мишина мама очень волнуется за сына, поэтому её интересует, в каком городе будет проходить олимпиада в определённые годы. Единственная информация, которой располагает мама Миши, — места проведения олимпиады в первые n лет. Помогите маме Миши, и она попросит Мишу не залить вашу квартиру.

Входные данные
В первой строке заданы три целых числа n, m и q (1 ≤ n, m ≤ 500000 , 1 ≤ q ≤ 20) — количество проведений олимпиады до введения правила, количество городов в Берляндии, готовых провести олимпиаду, и число лет, про которые маму Миши интересует место проведения олимпиады, соответственно.

В следующей строке содержится n целых чисел a_i (1 ≤ a_i ≤ m) — номера городов, в которых проводилась олимпиада в год i. Обратите внимание, что до принятия правила место проведения олимпиады могло выбираться произвольным образом.

В следующих q строках заданы целые числа k_i (n+1 ≤ k_i ≤ 10¹⁸) — номера годов, для которых маму Миши интересует место проведения олимпиады.

Выходные данные
Выведите q целых чисел. В строке с номером i выведите одно целое число — место проведения олимпиады в год k_i.

Примеры

№	Входные данные	Выходные данные
1	6 4 10 3 1 1 1 2 2 7 8 9 10 11 12 13 14 15 16	4 3 4 2 3 4 1 2 3 4
2	4 5 4 4 4 5 1 15 9 13 6	5 3 3 3

Иннокентий работает на блошином рынке, продавая посетителям всякий хлам необычные вещи. Недавно он нашёл у себя на складе старое прямоугольное покрывало. Как оказалось, это покрывало имеет сетчатую форму, то есть покрывало состоит из nm цветных лоскутков, разбитых на n строк и m столбцов.

Цветные лоскутки привлекли внимание Иннокентия, и он сразу же придумал, как можно заработать на своей находке. Если вырезать из покрывала подпрямоугольник, состоящий из трёх цветных полос, то потом этот подпрямоугольник можно будет продать как флаг какой-нибудь страны. В частности, Иннокентий считает, что подпрямоугольник будет достаточно похож на флаг какой-нибудь страны, если он будет состоять из трёх одноцветных полос одинаковой высоты, находящихся друг под другом. Разумеется, цвет верхней полосы не должен совпадать с цветом средней полосы, а цвет средней не должен совпадать с цветом нижней.

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



Входные данные
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 1000 ) — количество строк и столбцов в покрывале.

Каждая из следующих n строк описывает очередную строку покрывала и состоит из m строчных латинских букв от « a » до « z », где одинаковым цветам соответствуют одинаковые буквы, а разным цветам — разные буквы.

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

Примечание

Примеры

№	Входные данные	Выходные данные
1	4 3 aaa bbb ccb ddd	6

Федот — дизайнер, ему поручена ответственная работа по художественной укладке плитки черного и белого цвета. Его последнее задание — уложить черные и белые плитки в квадрате n × n.

Федот любит свою работу и всегда тщательно готовится к каждому проекту. Федот считает, что два квадрата похожи, если один из них можно получить из другого несколько раз заменив цвета в какой-то строке или столбце на противоположные. Федот заметил, что клиенты никогда не смотрят на всю работу целиком, обычно поле их зрения ограничивается квадратом k × k. Для оценки эскизов он ввел специальную величину — сложность. Она равна числу пар не похожих друг на друга квадратов k × k, которые встречаются в картине.

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

Прежде чем класть плитку, Федот подготовил несколько эскизов. Помогите Федоту вычислить их сложность.

Входные данные
Первая строка входного файла содержит два целых числа n и k (1 ≤ k ≤ n ≤ 500). Следуюшие n строк содержат описание эскиза. Каждая из них имеет длину n и состоит из символов b и w, которые соответствуют белому и черному цветам плиток.

Выходные данные
В первой строке выходного файла выведите одно целое число q — сложность картины.

Примеры

№	Входные данные	Выходные данные
1	2 1 bw wb	0
2	3 2 bwb wbb bbw	3

На планете Руук существует Большая Корпорация Маленьких Фей. Одним из видов деятельности, которым испокон веков занимаются ее сотрудницы, является посадка грядок с волшебными грибами. Каждый день, начиная с самого первого дня существования этой корпорации, феи создают одну новую грядку грибов. После этого с новой грядки два дня можно собирать споры, которыми размножаются эти грибы, а потом грядка будет поставлять уже только сам продукт — грибы.

Таким образом, если обозначить количество грибов, посаженных на грядке, созданной в день номер i, как c_i, то оно будет считаться по формуле c_i = c_i - 1 + c_i - 2. Так, в первый и второй дни было посажено по одному грибу, в третий — два, в четвертый — три, в пятый — пять и так далее.

Волшебные грибы являются самыми ценными сувенирами, которые путешественник может привезти с планеты Руук. Поэтому первым, что делает любой приезжий, становится поиск грядки с волшебными грибами. Однако, в последнее время все чаще стали появляться сообщения о поддельных волшебных грибах. Тщательное расследование показало, что это является следствием действий Маленькой Корпорации Больших Фей, которая сажает грядки с грибами, внешне не отличимыми, но далеко не такими ценными, как волшебные. Причем, создавая очередную грядку, эти феи сажают туда такое количество грибов, какое их соперницы никогда не сажали и не смогут посадить.

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

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

Первая строка входного файла содержит одно число N (1 ≤ N ≤ 1000000) — количество исследуемых грядок. Следующие n строк содержат по одному целому числу a_i — количества грибов на исследуемых грядках. Размер входного файла не превышает 1 Мб.

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

Для каждого числа, данного во входном файле, выведите «Yes», если грядка с таким количеством грибов является волшебной, и «No» — если не является. Ответы разделяйте переводами строк.

Примеры

№	Входные данные	Выходные данные
1	8 1 2 3 4 5 6 7 8	Yes Yes Yes No Yes No No Yes

У Индианы Джонса есть ключ от двери, ведущей к тайным богатствам инков. Ключ имеет форму правильного треугольника, который, в свою очередь, разбит на n² маленьких правильных треугольников, в каждом из которых написана одна десятичная цифра. Пример ключа приведен ниже на рисунке.


Джонс вставил треугольник в соответствующее треугольное отверстие в двери, и... она не открылась. Возможно, он вставил ключ неправильно, ведь его можно вставить тремя способами. Из-за того, что у Джонса осталась лишь одна попытка для того, чтоб открыть двери (в случае неудачи его убьют уже настигающие его кровожадные инки), он хочет знать как будет выглядеть ключ при его вставке в дверь другими двумя способами. После этого он сделает правильный выбор. Вас, как одного из двух своих помощников, он попросил показать ему только один из двух возможных вариантов. Внешний вид ключа, приведенного выше, при повороте против и по часовой стрелке изображен на рисунке ниже.


Поскольку вы не хотите смерти Индианы и хотите получить свою долю сокровищ, вам придется помочь ему!

Входные данные
В первой строке входного файла содержится одно целое число n (1 ≤ n ≤ 100). В следующих n строках описан сам треугольник. Строка входного файла, имеющая номер i + 1, содержит 2i - 1 цифру — содержание i-й строки ключа-треугольника.

Последняя строка содержит слово counterclockwise, если треугольник необходимо повернуть против часовой стрелки, и clockwise в противном случае.

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

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3 4 5 6 7 8 9 counterclockwise	9  4 8 7  1 3 2 6 5
2	3 1 2 3 4 5 6 7 8 9 clockwise	5  7 6 2  9 8 4 3 1

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

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

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

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

В первой строке находятся три целых числа h, w и k (1 ≤ h, w ≤ 30; 1 ≤ k ≤ 10). Каждая из последующих h строк содержит w символов. Символ «#» обозначает кнопку, а «.» — ее отсутствие.

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

Выведите единственное число — количество кодов, удовлетворяющих указанным требованиям.
 

Примеры

№	Входные данные	Выходные данные
1	2 2 2 .# ##	2
2	5 6 7 .#.... ##.##. ..#.#. .####. .....#	3