← К соревнованиям

Sort Me Round

Sapmles

Сложность: 66%

Даны 2 массива. Надо найти такие индексы i,j,ki, j, k (1i<j<k<n1 \le i < j < k < n), чтобы выполнялось условие: a[1]a[2]a[i]b[i+1]b[i+2]b[j]a[j+1]a[j+2]a[k]b[k+1]b[k+2]b[n]=0a[1] \oplus a[2] \oplus \dots \oplus a[i] \oplus b[i + 1] \oplus b[i + 2] \oplus \dots \oplus b[j] \oplus a[j + 1] \oplus a[j + 2] \oplus \dots \oplus a[k] \oplus b[k + 1] \oplus b[k + 2] \oplus \dots \oplus b[n] = 0, где \oplus – операция побитового исключающего ИЛИ.

Найдите количество троек, которое можно выбрать заданным образом, а так же любой подходящий отрезок.

Входные данные

В первой строке записано число nn (4n500 0004 \le n \le 500\ 000).

В следующей строке записано nn чисел a1,a2,ana_1, a_2 \dots, a_n. (0a[i]5 0000 \le a[i] \le 5\ 000)

В следующей строке записано nn чисел b1,b2,bnb_1, b_2 \dots, b_n. (0b[i]5 0000 \le b[i] \le 5 \ 000)

Выходные данные

В первой строке выведите одно число – количество способов выбрать тройку индексов заданным образом.

Во второй строке выведите три числа i,j,ki, j, kлюбую подходяющую тройку.

Подзадачи

баллынеобх. подзадачиограничения
1

5

-

n50n \le 50

2

11

1

n500n \le 500

3

17

2

n5 000n \le 5\ 000

4

22

3

n50 000n \le 50\ 000

5

45

4

n500 000n \le 500\ 000

STDINSTDOUT
6
5 3 3 2 5 8
9 3 1 4 6 6
2
2 4 5
5
1 4 1 1 0
3 0 1 0 1
2
1 2 4
5
1 2 3 4 5
5 4 3 2 1
0

Примечание

В первом примере подходят тройки индексов 1,4,51, 4, 5 и 2,4,52, 4, 5.

Во втором примере можно выбрать 1,2,41, 2, 4 и 1,3,41, 3, 4.

На рисунке XOR красных зон должен быть равен 0: