Назовем непустую строку x рефреном непустой строки y, если y является конкатенацией нескольких копий x. Например, рефренами строки abababab являются строки ab, abab и abababab, и только они.
Дана строка s из маленьких латинских букв. Сколько существует пар строк (x, y), таких что x и y — непустые префиксы s, и x — рефрен y?
В единственной строке находится строка s, состоящая из маленьких латинских букв. Длина строки не превышает 5 000 000.
Выведите одно число — ответ на задачу.
ababab
8
В свете недавних новостей о прослушке каналов связи, два непримиримых интернет-гиганта Урагании «Laim.UR» и «Xenda» решили подписать соглашение об установлении защищенного канала связи между дата-центрами друг друга. В Урагании n городов, но, к сожалению, ни в одном городе нет дата-центров обоих гигантов. Поэтому для формирования защищенного канала придется прокладывать междугородние линии связи.
Специалисты компаний определили m пар городов, которые можно соединить, проложив сегмент канала связи, и оценили стоимость создания такого сегмента для каждой из этих пар.
Результирующий канал может состоять из нескольких сегментов. Он должен начинаться в одном из городов, где находится дата-центр первой компании, может проходить через промежуточные города и должен заканчиваться в городе, где находится дата-центр второй компании.
Теперь необходимо определить минимальную стоимость защищенного канала, соединяющего два дата-центра компаний.
В первой строке находятся целые числа n и m (2 ≤ n ≤ 5 000, 1 ≤ m ≤ 105) — количество городов и количество пар городов, которые можно соединить сегментом канала связи.
Во второй строке находятся n целых чисел ai (0 ≤ ai ≤ 2). Если ai = 0, то в i-м городе нет дата-центра ни одного из гигантов. Если ai = 1, то в i-м городе есть дата-центр «Laim.UR», а если ai = 2, то в i-м городе находится дата-центр «Xenda». Гарантируется, что среди этих чисел есть как минимум одна единица и одна двойка.
В каждой из следующих m строк находится по три целых числа — si, ti и ci, которые означают, что города si и ti (1 ≤ si, ti ≤ n, si ≠ ti) можно соединить сегментом канала связи стоимостью ci (1 ≤ ci ≤ 105). Каждую пару городов можно соединить не более чем одним сегментом канала.
Если соединить защищенным каналом связи два дата-центра разных интернет-гигантов возможно, то выведите в выходной файл три числа: x, y и d, означающие, что между городами x и y возможно провести канал связи суммарной стоимостью d. В городе x должен находиться дата-центр «Laim.UR», в городе y — дата-центр «Xenda». Если существует несколько оптимальных ответов, выведите любой. Если провести искомый канал невозможно, выведите - 1.
6 7
1 0 1 2 2 0
1 3 3
1 2 4
2 3 3
2 4 2
1 6 5
3 5 6
5 6 1
3 4 5
В прошлом существовало большое и могучее королевство, которое называлось Лордаэрон. Его правителем был мудрый король Теренас. В Лордаэроне была могучая армия и бесчисленное мно- жество замков и крепостей. Для управления такой военной машиной, Теренас выбрал несколько генералов из числа наиболее верных ему людей. Как-то раз первый генерал заявил: "Мой король, небезопасно оставлять наш главный замок без хорошей защиты. Позвольте мне построить стену вокруг него". Конечно, король согласился (в конце концов, еще одна стена ничего не ухудшит). Когда стена была закончена, другой генерал заявил: "Мой король, все еще небезопасно оставлять наш главный замок без хорошей защиты. Позвольте мне построить еще одну стену вокруг него". Король согласился. После завершения второй стены еще один генерал сказал то же самое ... . В итоге, было построено N стен вокруг замка и вся площадь между стенами была занята полями пшеницы. Однажды враги Лордаэрона осадили его основной замок. Но что они могу сделать со стенами? Они не могут забраться на них. Но зато у них есть луки и стрелы. И еще врагам известно, что все, что находится между стенами, очень хорошо горит. В течение осады, разведка Лордаэрона выяснила координаты всех точек, в которые попали стрелы. И король Теренас подсчитал ущерб, нанесенный врагами полям — другими словами площадь сгоревших полей. Сможете ли вы повторить это? Вы можете предполагать верными следующие факты. Замок очень мал и может считаться точкой — началом координат. Все стены являются выпуклыми многоугольниками. Они не касаются друг друга и не пересекаются друг с другом. Также, начало координат находится внутри всех многоугольников. Точки выстрелов не находятся на стенах. Если точка выстрела находится вне самой внешней стены, ничего не сгорит. Иначе сгорит вся площадь, до которой огонь может добраться из точки выстрела (а огонь легко распространяетяс по полям, но не может пересекать стены). Ваша задача — посчитать суммарную площадь того, что сгорит.
В первой строке находится число стен N (1 ≤ N ≤ 105). Далее следует N блоков. В первой строке каждого блока находится число K — количество вершин в многоугольнике, представляющим стену. Далее в K строках находится по два числа X и Y — координаты вершины многоугольника. Каждый многоугольник будет задан в порядке обхода против часовой стрелки. У каждого многоугольника ненулевая площадь. Вы можете предполагать, что общее количество точек во всех многоугольниках не превосходит 105 . Стены будут даны в произвольном порядке. Далее следует количество точек выстрелов, M (0 ≤ M ≤ 105). Далее следует M строк с координатами M точек выстрела. Все координаты во входном файле являются целыми и не превосходят 106 по абсолютной величине.
Выведите единственное число с не менее чем шестью знаками после десятичной точки — общую площадь сгоревших полей.
3
4
-10 -10
10 -10
10 10
-10 10
4
20 20
-20 20
-20 -20
20 -20
4
30 -30
30 30
-30 30
-30 -30
3
1 1
22 23
111 123
2400.0
Вася выписал на доске в каком-то порядке все числа от 1 по N, каждое число ровно по одному разу. Количество чисел оказалось довольно большим, поэтому Вася не может окинуть взглядом все числа. Однако ему надо всё-таки представлять эту последовательность, поэтому он написал программу, которая отвечает на вопрос — сколько среди чисел, стоящих на позициях с x по y, по величине лежат в интервале от k до l. Сделайте то же самое.
В первой строке лежит два натуральных числа — 1 ≤ N ≤ 100 000 — количество чисел, которые выписал Вася и 1 ≤ M ≤ 100 000 — количество вопросов, которые Вася хочет задать программе. Во второй строке дано N чисел — последовательность чисел, выписанных Васей. Далее в M строках находятся описания вопросов. Каждая строка содержит четыре целых числа 1 ≤ x ≤ y ≤ N и 1 ≤ k ≤ l ≤ N.
Выведите M строк, каждая должна содержать единственное число — ответ на Васин вопрос.
4 2
1 2 3 4
1 2 2 3
1 3 1 3
1
3