Я говорю на языке китов
Согласно Википедии, матрица Уолша — это квадратная матрица, размер которой является степенью 2, элементы которой равны +1 или -1, и обладающая свойством, что скалярное произведение любых двух различных строк (или столбцов) равно нулю. Ниже представлены первые три матрицы Уолша. (Серые линии — это воображаемые линии, используемые только для иллюстрации).
Матрица Уолша размера 2N+1 может быть построена как "объединение" 4 матриц Уолша размера 2N, расположенных таким образом, что правая нижняя матрица инвертирована, тогда как остальные 3 матрицы остаются неизменными, то есть:
Пронумеруем строки данной матрицы Уолша сверху, начиная с 0. Аналогично, пронумеруем столбцы слева, начиная с 0. Даны четыре целых числа N, R, S и E. Напишите программу, которая построит матрицу Уолша размера 2N и вычислит сумму всех чисел в строке #R между столбцами #S и #E (включительно).
Входные данные
Ваша программа будет тестироваться на одном или нескольких тестовых случаях. Каждый тестовый случай задается одной строкой, содержащей четыре целых числа в следующем порядке: N, R, S и E, где 0 ≤ N ≤ 60, 0 ≤ R < 2^N, 0 ≤ S ≤ E < 2^N, и E-S ≤ 10000. Последняя строка входного файла содержит четыре -1 и не является частью тестовых случаев.
Выходные данные
Для каждого тестового случая выведите результат в одной строке.