Феникс любит играть с битами — особенно используя битовые операции AND, OR и XOR. У него есть \(n\) целых чисел \(a_1, a_2, \dots, a_n\) и \(q\) запросов, каждый одного из следующих типов:
- заменить все числа \(a_i\), для которых \(l \le a_i \le r\), на \(a_i\) AND \(x\);
- заменить все числа \(a_i\), для которых \(l \le a_i \le r\), на \(a_i\) OR \(x\);
- заменить все числа \(a_i\), для которых \(l \le a_i \le r\), на \(a_i\) XOR \(x\);
- вывести количество различных чисел \(a_i\), для которых \(l \le a_i \le r\).
В каждом запросе Феникса \(l\), \(r\) и \(x\) заданы. Заметим, что он рассматривает значения чисел, а не их индексы.
Выходные данные
Выведите ответ для каждого запроса четвертого типа (\(t=4\)).
Примечание
В первом примере:
- В первом запросе, \(2\) заменяется на \(2\) AND \(2 = 2\), и \(3\) заменяется на \(3\) AND \(2 = 2\). Множество чисел становится \(\{1, 2, 4, 5\}\).
- Во втором запросе, есть \(3\) различных числа от \(2\) по \(5\): \(2\), \(4\) и \(5\).
- В третьем запросе, \(2\) заменяется на \(2\) XOR \(3 = 1\), \(4\) заменяется на \(4\) XOR \(3 = 7\), и \(5\) заменяется на \(5\) XOR \(3 = 6\). Множество чисел становится \(\{1, 6, 7\}\).
- В четвертом запросе, есть \(2\) различных числа от \(1\) по \(6\): \(1\) и \(6\).
- В пятом запросе, \(1\) заменяется на \(1\) OR \(8 = 9\). Множество чисел становится \(\{6, 7, 9\}\).
- В шестом запросе, есть одно различное число от \(8\) по \(10\): \(9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6
5 4 3 2 1
1 2 3 2
4 2 5
3 2 5 3
4 1 6
2 1 1 8
4 8 10
|
3
2
1
|
|
2
|
6 7
6 0 2 3 2 7
1 0 4 3
2 6 8 4
4 0 7
3 2 5 3
1 0 1 2
4 0 3
4 2 7
|
5
1
2
|