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