Hay dos arreglos de largo \(n\): \(A\), de ceros y unos, y \(B\), de enteros. Se procesan \(q\) operaciones:

• 1 l r: invertir \(A_i\) (0 pasa a 1 y 1 a 0) para todo \(l \le i \le r\);
• 2 p 0: para todo \(i\), sumar \(A_i \cdot p\) a \(B_i\);
• 3 0 0: informar la suma de todos los elementos de \(B\).

Entrada

La primera línea tiene \(n\) y \(q\) \((1 \le n, q \le 10^5)\). La segunda tiene \(A\), la tercera \(B\) \((0 \le B_i \le 10^9)\), y siguen \(q\) líneas con las operaciones (\(0 \le l \le r < n\), \(1 \le p \le 10^6\)).

Salida

Para cada operación de tipo 3, una línea con la suma. Cabe en un entero de 64 bits.

Ejemplo 1

Entrada

3 3
1 0 1
0 0 0
1 1 1
2 1 0
3 0 0

Salida

3

Ejemplo 2

Entrada

1 2
1
5
2 3 0
3 0 0

Salida

8