>Во время исследований, посвященных появлению жизни на планете Олимпия, учеными было сделано несколько сенсационных открытий:
Чтобы не придумывать названия во время исследований, ученые пронумеровали все виды организмов, которые когда-либо существовали на планете. Для этого они нарисовали дерево эволюции с корнем Bitozoria Programulis, которая получила номер 1. Далее нумеровали виды каждого шага эволюции слева направо. Таким образом непосредственные подвиды Bitozoria Programulis получили номера 2 и 3. Следующими были занумерованы виды третьего шага эволюции – подвиды вида 2 получили номера 4 и 5, а вида 3 – номера 6 и 7, и т.д.
Напишите программу, которая по номерам двух видов вычислит номер вида их ближайшего общего предка в дереве эволюции.
Первая строка входного файла содержит целое число N (1≤N≤100) – количество этапов эволюции, которые произошли на планете Олимпия до текущего времени. Вторая и третья строки файла содержат по одному натуральному числу, которые представляют номера видов, для которых требуется найти номер их ближайшего общего предка.
Единственная строка выходного файла должна содержать натуральное число – номер ближайшего предка для двух видов.
4 15 12
3
18 233016 233008
14563
Ограничение по времени: 0.2 секунды
На планете Олимпия рабочие строят новую дамбу. Часть плоскости, на которой проводятся строительные работы, имеет вид прямоугольника размером 1 x \(L\) метров, на котором введены координаты, как показано на рисунке.
Для поднятия ландшафта используют специально разработанные магические импульсаторы. Если магический импульсатор силой \(H\) поставить в точку с \(X\)-координатой \(p\), то в каждой точке \(q\) отрезка [\(p\)–\(H\);\(p\)] на оси \(X\) рельеф поднимается на \(q\)–\(p\)+\(H\) метров по всей его ширине (то есть для произвольного \(Z\) от 0 до 1), а в каждой точке \(q\) отрезка [\(p\);\(p\)+\(H\)] рельеф поднимается на \(H\)+\(p\)–\(q\) метров по всей его ширине, в остальных точках ландшафт остается неизменным (см. рисунок).
Во время строительства рабочие время от времени интересуются объёмом части дамбы, находящейся над некоторым прямоугольником.
Напишите программу, которая поможет рабочим в их расчётах.
В первой строке входного файла содержатся два целых числа: N – количество операций, которые будут выполнять рабочие (1≤\(N\)≤100000), и \(L\) – длина прямоугольника (1≤\(L\)≤100000).
В следующих \(N\) строках содержатся описания операций: первое число строки – номер операции, где „1” означает, что рабочие собираются поставить магический импульсатор, „2” – рабочие хотят узнать некоторый объём. Если операция имеет код „1”, то далее идут два целых числа \(p\) и \(H\) (0≤\(p\)≤\(L\); 1≤\(H\)≤\(L\)), то есть импульсатор силой \(H\) ставят в позицию p (на оси \(X\)). Если операция имеет код „2”, то далее идут два целых числа \(A\) и \(B\) (0≤\(A\)<\(B\)≤\(L\)); это означает, что рабочие хотят узнать объём части дамбы, которая находится над прямоугольником от \(A\) до \(B\) по оси \(X\), и от 0 до 1 по оси \(Z\).
Создайте выходной файл, в котором для каждой операции, указанной во входном файле, выведите строку со следующей информацией.
Если операция есть „1”, то выведите число „-1” без кавычек. Если операция есть „2”, то выведите число округленное вниз до ближайшего целого, равное объёму части дамбы, которая находится над прямоугольником от \(A\) до \(B\) по оси \(X\), и от 0 до 1 по оси \(Z\), как показано на рисунке.
2 13 1 7 5 2 5 9
-1 16
Петрик и Василько — настоящие друзья, поэтому они постоянно задают друг другу всевозможные интересные задачи. Однако Василько всегда с легкостью решает задачи своего друга, поэтому Петрик решил придумать по-настоящему сложную задачу. И вот что у него получилось. Будем называть число b подчислом числа a , если из числа a можно вычеркнуть некоторые цифры так, что цифры, которые остались, образуют число b . Задано n -цифровое число x . Обозначим как x k наибольшее k -цифровое подчисло числа x . Необходимо ответить на m запросов. Каждый запрос состоит из двух цифр - k и l . Ответом на запрос является l -я цифра числа x k . На этот раз задача действительно заставила Василько задуматься. А сможете ли вы решить ее быстрее его?
В первой строке входного файла содержится целое число x длины n ( 1 ≤ n ≤ 100 000 ). Во второй строке содержится число m ( 1 ≤ m ≤ 50 000 ). В следующих m строках содержится по два числа k i , l i ( 1 ≤ k i ≤ n , 1 ≤ l i ≤ k i ) — параметры i -го запроса.
Выходной файл должен содержать одну строку длины m , i -й символ которого является ответом на i -й запрос.
31415926 7 2 2 3 1 1 1 4 3 5 2 8 2 7 3
6992511