Baby Ehab has finished studying bitwise operations. He especially loved the two operations bitwise $O R$ and bitwise $X O R$ (of course).
He thought he'd mess with Baby Badawy and play with.. Well.. His cubes. Baby Badawy had an array $a$ of cubes, lined up from left to right. The $i_{t h}$ cube had a number $a_i$ written on it. On each of the following $q$ operations, he would do one of the following 2 updates:
Baby Badawy decided to make a stand against Ehab's bullying and all the babysitters were behind our golden boy. He told Ehab that he can tell him the sum of all the numbers in the array after each operation.
You, a stranger, decided to help our golden boy. Can you?
The first line contains 2 integers $n$ and $q$ $(1 <= n, q <= 3 times 10^5)$, the number of elements in the array $a$ and the number of operations.
The second line contains $n$ space-separated integers denoting the array $a$ $(1 <= a_i <= 3 times 10^5)$.
The following $q$ lines will each contain an update as described in the statement $(1 <= l_i <= r_i <= n)$.
After each update, print the sum of the array on a single line.
## Input
The first line contains 2 integers $n$ and $q$ $(1 <= n, q <= 3 times 10^5)$, the number of elements in the array $a$ and the number of operations.The second line contains $n$ space-separated integers denoting the array $a$ $(1 <= a_i <= 3 times 10^5)$.The following $q$ lines will each contain an update as described in the statement $(1 <= l_i <= r_i <= n)$.
## Output
After each update, print the sum of the array on a single line.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ 1 \leq n \leq 6 $, be the number of minions.
For each $ i \in \{1, \dots, n\} $, let $ a_i \in \mathbb{Z}_{\geq 0} $ denote the attack power and $ h_i \in \mathbb{Z}^+ $ the health of minion $ i $.
Let $ \mathcal{P} $ be the set of all $ n! $ permutations of $ \{1, \dots, n\} $, representing all possible attack orders.
For a permutation $ \pi \in \mathcal{P} $, define the state evolution $ S_\pi = (s_1, \dots, s_n) \in \{0,1\}^n $, where $ s_i = 1 $ iff minion $ i $ survives the entire process under order $ \pi $, and $ s_i = 0 $ otherwise.
The state evolves as follows:
- Initialize health vector $ H = (h_1, \dots, h_n) $.
- For each position $ k = 1 $ to $ n $:
- Let $ i = \pi_k $.
- If $ H_i \leq 0 $, skip.
- Else, let $ T = \{ j \neq i \mid H_j > 0 \} $.
- If $ T = \emptyset $, skip.
- Else, uniformly sample $ j \in T $, and update:
$$
H_i \leftarrow H_i - a_j, \quad H_j \leftarrow H_j - a_i.
$$
Define survival indicator: $ s_i(\pi) = \mathbb{I}(H_i > 0) $ after full execution under $ \pi $.
**Constraints**
1. $ 1 \leq n \leq 6 $
2. $ 0 \leq a_i \leq 10^6 $, $ 1 \leq h_i \leq 10^6 $ for all $ i $
**Objective**
For each minion $ i \in \{1, \dots, n\} $, compute the survival probability:
$$
p_i = \frac{1}{n!} \sum_{\pi \in \mathcal{P}} s_i(\pi)
$$
Output $ p_1, p_2, \dots, p_n $, each as a decimal number.