У вас есть n детских игрушечных кубиков. Вы хотите построить из них крепость.
Крепость — это последовательность из башен, составленных из кубиков. При этом в каждой башне может быть только нечетное число кубиков.
Ваша задача — посчитать количество крепостей, которые можно составить ровно из n кубиков. Две крепости считаются различными, если существует такое i, что количество кубиков в i-ой слева башне первой крепости отличается от количества кубиков в i-ой слева башне второй крепости.
В первой строке записано целое число n (1 ≤ n ≤ 70).
Выведите количество крепостей, которые можно составить ровно из n кубиков.
Обратите внимание, что ответ может не помещаться в 32-битный знаковый тип.
1
1
2
1
4
3
10
55
Вам даны два числа n и k, нужно вывести все разбиения n элементного множества на k множеств. Строго следуйте формату выходных данных при выводе разбиений.
В первой строке записаны два целых числа n и k (1 ≤ k ≤ n ≤ 11).
Выведите все разбиения в лексикографическом порядке. Элементы в множествах разбиения сортируйте в порядке возрастания. Сами множества в разбиениях сортируйте в лексикографическом порядке. Не выводите никаких лишних пробелов, строго следуйте формату, указанному в тестовых примерах.
1 1
[1]
3 2
[1][2,3]
[1,2][3]
[1,3][2]
4 3
[1][2][3,4]
[1][2,3][4]
[1][2,4][3]
[1,2][3][4]
[1,3][2][4]
[1,4][2][3]
5 3
[1][2][3,4,5]
[1][2,3][4,5]
[1][2,3,4][5]
[1][2,3,5][4]
[1][2,4][3,5]
[1][2,4,5][3]
[1][2,5][3,4]
[1,2][3][4,5]
[1,2][3,4][5]
[1,2][3,5][4]
[1,2,3][4][5]
[1,2,4][3][5]
[1,2,5][3][4]
[1,3][2][4,5]
[1,3][2,4][5]
[1,3][2,5][4]
[1,3,4][2][5]
[1,3,5][2][4]
[1,4][2][3,5]
[1,4][2,3][5]
[1,4][2,5][3]
[1,4,5][2][3]
[1,5][2][3,4]
[1,5][2,3][4]
[1,5][2,4][3]
Вам дан массив a1, a2, ..., an, состоящий из целых положительных чисел. Так же вам даны m запросов вида li, ri. В ответ на i-ый запрос нужно вывести наибольший общий делитель чисел ali, ali + 1, ..., ari.
В первой строке записаны два целых числа n, m (1 ≤ n, m ≤ 50000). Во второй строке записан массив a1, a2, ..., an (1 ≤ ai ≤ 109). В следующих m строках записаны пары целых чисел li, ri (1 ≤ li ≤ ri ≤ n) — запросы.
В ответ на каждый запрос выведите наибольший общий делитель элементов массива из соответствующего отрезка.
10 13
18 12 18 12 12 15 18 9 18 6
4 9
10 10
8 10
6 6
2 6
4 5
7 9
1 7
1 5
1 1
3 4
6 7
6 9
3
6
3
15
3
12
9
3
6
18
6
3
3