Задача A. Перестановки с подстрокой ≡

Условие

Даны строки S и P, состоящие из малых латинских букв. Требуется определить сколько различных слов, составленных из букв строки S, содержат в себе подстроку P.

Например, если S = dcba, P = bc, то получится 11 строк: bc, abc, bca, dbc, bcd, adbc, dabc, abcd, dbca, bcad, bcda.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

dbca
bc

11

xyz
xx

0

Задача B. Ферзи на шахматной доске ≡

Условие

Ферзь — шахматная фигура, которая может двигаться на любое число клеток по горизонтали, вертикали или диагонали.

На бесконечной шахматной доске расположены K ферзей. Требуется вывести прямоугольный фрагмент шахматной доски, заданный двумя противоположными клетками с координатами (X_A; Y_A) и (X_B; Y_B).

Клетки чёрного цвета обозначаются символом '#' (ASCII 35), клетки белого цвета обозначаются символом '.' (точка, ASCII 46), клетка с ферзем обозначается символом 'X' (ASCII 88), клетка, в которую может походить ферзь обозначается символом '*' (ASCII 42).

Ось ординат (OY) направлена вертикально вниз. Клетка с координатами (1; 1) имеет чёрный цвет.

Формат входного файла

Во входном файле содержатся числа X_A Y_A X_B Y_B K

Далее следуют K пар чисел — X_i Y_i

Формат выходного файла

Выходной файл должен содержать изображение заданного фрагмента шахматной доски.

Ограничения

1 ≤ X_i, Y_i ≤ 2³¹−1

0 ≤ K ≤ 10⁵

1 ≤ |X_A − X_B|, |Y_A − Y_B| ≤ 500

В одной клетке не может находиться более одного ферзя

Примеры тестов

1 8 8 1
2
7 1
3 5

******X*
.#*#.***
*.*.*.*.
.***.#*#
**X*****
.***.#*#
*.*.*.*.
.#*#.**#

6987879 87979870 6987899 87979879
1
3271487 84263477

.*.#.#.#.#.#.#.#.#.#.
#.*.#.#.#.#.#.#.#.#.#
.#.*.#.#.#.#.#.#.#.#.
#.#.*.#.#.#.#.#.#.#.#
.#.#.*.#.#.#.#.#.#.#.
#.#.#.*.#.#.#.#.#.#.#
.#.#.#.*.#.#.#.#.#.#.
#.#.#.#.*.#.#.#.#.#.#
.#.#.#.#.*.#.#.#.#.#.
#.#.#.#.#.*.#.#.#.#.#

Задача C. Есть ли прогрессия? ≡

Условие

Даны целые положительные числа S и k. Требуется найти такие целые положительные числа a и b, что:

1. a ≤ k ≤ b
2. Сумма всех целых чисел от a до b включительно равна S

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

12 4

3 5

13 12

0

Задача D. Хоттабыч и векторы на плоскости ≡

Условие

Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб изучил планиметрию. Особенно Хоттабычу понравились векторы. Ему стало интересно, можно ли для набора из N векторов подобрать угол φ так, чтобы, повернув некоторую часть векторов на угол φ по часовой стрелке, а остальную часть — на угол φ против часовой стрелки и сложив получившиеся векторы, получить вектор не длиннее самого длинного вектора в данном наборе.

Помогите Хоттабычу решить данную задачу.

Формат входного файла

Во входном файле содержится число N.

Далее следует N пар чисел — координаты векторов X_i Y_i.

Формат выходного файла

• Если нельзя подобрать угол φ, выходной файл должен содержать единственное слово NO.

• В противном случае в первой строке входного файла должно содержаться единственное число — угол φ в градусах с точностью не менее 10⁻⁵

  Во второй строчке входного файла должна содержаться последовательность из символов '+' (ASCII 43) и '-' (ASCII 45) длиной в N символов. Символ '+' в i-ой позиции означает, что i−ый вектор требуется повернуть против часовой стрелки, а символ '-' — поворот i-го вектора по часовой стрелке.

Ограничения

2 ≤ N ≤ 10⁵

−1000 ≤ X_i, Y_i ≤ 1000

0 ≤ φ ≤ 180

Все входные данные — целые числа

Примеры тестов

2
2 2
-3 5

47.5
-+

3
0 4
3 4
-3 4

90
+--