Кратко напомним правила игры «Ним». Имеется \(n\) кучек камней, при этом в кучке \(i\) изначально лежит какое-то число камней. Два игрока по очереди выбирают непустую кучку и берут из нее произвольное положительное (строго больше \(0\)) количество камней. Проигрывает тот, кто не может сделать ход.
Дан массив \(a\), состоящий из \(n\) целых чисел. Артем и Руслан решили играть в Ним на подотрезках массива. Каждый из \(q\) раундов определяется отрезком \((l_i, r_i)\), где элементы массива \(a_{l_i}, a_{l_i+1}, \dots, a_{r_i}\) рассматриваются как размеры кучек камней.
До начала игры Руслан может удалить любое количество кучек из выбранного подотрезка. Однако хотя бы одна кучка должна остаться, поэтому в рамках одного раунда он может удалить не более \((r_i - l_i)\) кучек. Разрешается удалить \(0\) кучек. После удаления ребята играют в Ним на всех оставшихся кучках из этого отрезка.
Все раунды независимы: удаления, произведенные в одном раунде, не влияют на исходный массив или другие раунды.
Руслану нужно удалить как можно больше кучек так, чтобы Артем, который будет ходить первым, проиграл.
Для каждого раунда определите:
- максимальное количество кучек, которые Руслан может удалить;
- количество способов выбрать максимальное количество кучек для удаления.
Два способа считаются различными, если существует такая позиция \(i\), что в одном из способов кучка на позиции \(i\) удаляется, а во втором — нет. Поскольку количество способов может быть большим, выведите его по модулю \(998\,244\,353\).
Если в каком-то раунде Руслан не может сделать так, чтобы Артем проиграл, выведите для этого раунда одно число -1.