На фабрике производят цветные кубики. Для их изготовления берётся заготовка — деревянный брусок $$$a \times b \times c$$$. Сначала его распиливают на $$$a \cdot b \cdot c$$$ единичных кубиков, а потом каждый кубик окрашивается со всех сторон.
Однако из-за ошибки в программе для станка, написанной с помощью системы вайб-кодинга «Кодер 239», в этот раз всё произошло наоборот: сначала стороны бруска были покрашены со всех сторон, а затем он был распилен на единичные кубики. Из-за этого у разных кубиков в этой партии могло оказаться разное количество покрашенных сторон.
Для оценки ущерба необходимо посчитать количество кубиков, у которых покрашено ровно $$$k$$$ сторон.
Единственная строка содержит четыре числа: $$$a$$$, $$$b$$$, $$$c$$$ $$$(1 \le a, b, c \le 10^5)$$$ — размеры бруска, — и число покрашенных сторон кубика $$$k$$$ $$$(0 \le k \le 6)$$$.
Выведите одно число — количество единичных кубиков с заданным числом покрашенных сторон.
В этой задаче 20 тестов, каждый оценивается независимо в 5 баллов.
В этой задаче во время тура вам сообщается результат проверки на каждом тесте.
3 3 3 3
8
4 2 1 3
4
Рассмотрим массив чисел $$$b_1, \dots, b_m$$$. Скользящими окнами длины $$$k$$$ ($$$k \le m$$$) на этом массиве называются все подотрезки длины $$$k$$$, то есть отрезки $$$[b_1, \dots, b_k]$$$, $$$[b_2, \dots, b_{k + 1}]$$$, $$$\dots,$$$ $$$[b_{m-k+1}, \dots, b_m]$$$.
Дан массив чисел $$$a_1, \dots, a_n$$$ длины $$$n$$$. Ответьте на $$$q$$$ запросов следующего вида про этот массив: для заданных $$$l$$$, $$$r$$$, $$$k$$$ найти сумму минимумов на скользящих окнах длины $$$k$$$ на подотрезке $$$[a_l, \dots, a_r]$$$.
В первой строке входных данных даны два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 100\,000$$$) — длина массива и количество запросов.
Во второй строке даны $$$n$$$ целых чисел $$$a_1, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — значения чисел в массиве.
В следующих $$$q$$$ строках даны запросы. В $$$i$$$-й из них даны три целых числа $$$l_i$$$, $$$r_i$$$ и $$$k_i$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le k \le r - l + 1$$$) — левая и правая границы отрезков и длина скользящего окна в $$$i$$$-м запросе.
Выведите $$$q$$$ строк с ответами на запросы. В $$$i$$$-й строке выведите единственное число — сумму минимумов на скользящих окнах длины $$$k_i$$$ на подотрезке $$$[a_{l_i}, \dots, a_{r_i}]$$$.
| Подзадача | Баллы | Дополнительные ограничения | Необх. подзадачи |
| 1 | 6 | $$$n, q \le 300$$$ | |
| 2 | 12 | $$$n, q \le 4000$$$ | 1 |
| 3 | 8 | $$$n, q \le 10\,000$$$ | 1, 2 |
| 4 | 11 | $$$n \le 4\,000$$$ | 1, 2 |
| 5 | 10 | $$$k_i$$$ равны во всех запросах | |
| 6 | 14 | $$$a_i \le 2$$$ | |
| 7 | 7 | $$$a_i \le 20$$$ | 6 |
| 8 | 15 | $$$l_i = 1, r_i = n$$$ | |
| 9 | 17 | нет | 1–8 |
6 34 6 1 2 5 32 5 22 4 11 6 6
4 9 1
Даны два массива неотрицательных целых чисел $$$A=[a_1, a_2, \ldots, a_n]$$$ и $$$B=[b_1, b_2, \ldots, b_m]$$$.
Пусть $$$S(i) = \{j | (a_i \oplus b_j) \leq x\}$$$. Иными словами, $$$S(i)$$$ это множество всех индексов $$$j$$$ массива $$$B$$$, для которых побитовое исключающее или $$$a_i$$$ и $$$b_j$$$ не превосходит $$$x$$$.
Найдите минимальное число $$$k$$$, чтобы можно было покрасить элементы массива $$$A$$$ в $$$k$$$ цветов таким образом, что если $$$S(x)$$$ и $$$S(y)$$$ пересекаются, то $$$x$$$ и $$$y$$$ покрашены в разный цвет.
Иначе говоря, можно найти такие $$$c_1, c_2, \ldots, c_n$$$, что $$$1 \le c_i \le k$$$, и при этом если $$$S(x) \cap S(y) \neq \varnothing$$$, то $$$c_x \neq c_y$$$.
Напомним, что побитовое «исключающее или» ($$$\oplus$$$, xor) двух целых неотрицательных чисел определено следующим образом: запишем оба числа в двоичной системе счисления, $$$i$$$-й двоичный разряд результата равен 1, если ровно у одного из аргументов он равен 1. Например, ($$$14$$$ xor $$$7$$$) = ($$$1110_2 \oplus 0111_2$$$) = $$$1001_2$$$ = $$$9$$$. Эта операция реализована во всех современных языках программирования, в языках C++, Java и Python она записывается как «^{}», в Паскале как «xor».
Входные данные для этой задачи содержат несколько тестовых примеров.
Первая строка ввода содержит одно целое число $$$t$$$ $$$(1 \le t \le 100)$$$ — количество тестовых примеров.
Далее следуют описания тестовых примеров.
В первой строке каждого тестового примера записаны три целых числа $$$n$$$, $$$m$$$ и $$$x$$$ ($$$1 \le n, m \le 500\,000$$$, $$$0 \leq x \lt 2^{30}$$$).
Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — элементы массива $$$A$$$ ($$$0 \le a_i \lt 2^{30}$$$).
В третьей строке записаны $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ — элементы массива $$$B$$$ ($$$0 \le b_i \lt 2^{30}$$$).
Гарантируется, что как сумма значений $$$n$$$, так и сумма значений $$$m$$$ по всем тестовым примерам не превосходит $$$500\,000$$$.
Для каждого тестового примера выведите одно целое число — минимальное искомое $$$k$$$.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи | |
| 1 | 5 | $$$n \le 2$$$ | — | |
| 2 | 5 | $$$n \le 5$$$ | 1 | |
| 3 | 5 | $$$n \le 15$$$ | 1,2 | |
| 4 | 5 | $$$n \le 100$$$ | 1–3 | |
| 5 | 5 | $$$n \le 2\,000$$$ | 1–4 | |
| 6 | 10 | $$$n \le 5\,000$$$ | 1–5 | |
| 7 | 5 | $$$n \le 100\,000$$$, $$$m = 2$$$ | — | |
| 8 | 10 | $$$n \leq 100\,000$$$, $$$m = 3$$$ | — | |
| 9 | 5 | $$$n, m \le 100\,000$$$; $$$a_i, b_i, k | lt; 2$$$ | — |
| 10 | 10 | $$$n, m \le 100\,000$$$; $$$a_i, b_i, k | lt; 4$$$ | 9 |
| 11 | 35 | нет | 1–10 |
32 2 00 01 15 5 30 1 2 3 40 1 2 3 45 5 40 1 2 3 40 1 2 3 4
1 4 5