Magical Segment Tree Expectation

Little Kobayashi is a programming expert and, unsurprisingly, her friend Konna has become fascinated by the "magic" of humans. Today, Konna learned about a mysterious magic called the segment tree which can maintain information about an interval. Konna even wrote a segment tree to maintain the sum over an interval. However, since she didn’t know about lazy propagation, she implemented all range addition operations in a brute‐force manner by updating every affected point.

for(int i=l;i<=r;i++) T.change(1,1,n,i,addv);

In this segment tree, every node stores the sum over its managed interval (that is, if a node covers the interval \([L,R]\), its value is \(\sum_{i=L}^{R}a_i\)). Suddenly, Konna thought up the following problem:

After performing a range addition update on the segment tree, we start at the root and, at each internal node, choose one of its two children uniformly at random until we reach a leaf node. We then sum the values of all nodes along this random path. What is the expected value of this sum? Each query also provides an integer qwq and it is guaranteed that the product of the expected value and qwq is an integer.

---

Problem Details

Note: The segment tree is built in the standard way. In particular, the tree is constructed by:

• If the current segment is a single element, it is a leaf.
• Otherwise, let mid = \(\lfloor(l+r)/2\rfloor\). The left child covers \([l,mid]\) and the right child covers \([mid+1,r]\).

Thus, for each leaf at index \(i\), if its depth (the number of recursive calls needed to reach it) is \(d_i\) (with the root having depth 0), then the probability that a node on its path at depth \(j\) is chosen is \((1/2)^j\) (the root is always chosen). Hence the total contribution weight for a[i] is

[ w_i = \sum_{j=0}^{d_i} \left(\frac12\right)^j = \frac{2^{d_i+1}-1}{2^{d_i}} = 2 - \frac{1}{2^{d_i}}. ]

Let \(S = \sum_{i=1}^{n} a[i] \times w_i\). Then the expected sum along the random path is \(\frac{S}{2^D}\) where \(D = \max_{1\le i\le n}d_i\) (this normalization comes from converting the weights to a common denominator). For each update, you will be given four integers \(l, r, addv, qwq\). For each index \(i\) in \([l,r]\), add \(addv\) to \(a[i]\). After the update, report the value

[ \text{answer} = \frac{qwq \times S}{2^D}, ]

which is guaranteed to be an integer.

---

Input Format

Output Format

---

Example

Input:
3 2
1 2 3
2 3 1 4
1 1 2 2

Output:
52
33

Explanation (for the first query):

The segment tree is built on \(n=3\) elements. Suppose via a DFS-based construction the depths of the leaves are: \(d_1=2, d_2=2, d_3=1\), hence \(D=2\). The weights are computed as:

• For index 1 and 2: \(w=\frac{2^{3}-1}{2^{2}}=\frac{8-1}{4}=\frac{7}{4}\)
• For index 3: \(w=\frac{2^{2}-1}{2^{1}}=\frac{4-1}{2}=\frac{3}{2}\)

Thus, initially \(S=1\times\frac{7}{4}+2\times\frac{7}{4}+3\times\frac{3}{2}=\frac{7+14+18}{4}=\frac{39}{4}\). After the update on indices 2 to 3 adding 1, \(S\) becomes \(1\times\frac{7}{4}+3\times\frac{7}{4}+4\times\frac{3}{2}=\frac{52}{4}\). Multiplying by \(qwq=4\) and dividing by \(2^D=4\) gives \(52\).

inputFormat

Input is read from standard input. The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq 10^5) \). The second line contains \(n\) integers \(a[1], a[2], \dots, a[n]\) \( (|a[i]| \leq 10^9) \). Then follow \(m\) lines, each containing four integers \(l, r, addv, qwq\) \(1 \leq l \leq r \leq n, |addv| \leq 10^9, 1 \leq qwq \leq 10^9\). It is guaranteed that \(qwq \times E\) is an integer for each query, where \(E\) is the expected sum defined above.

Format:
n m
a[1] a[2] ... a[n]
l r addv qwq
...

outputFormat

For each query, output the integer answer on a new line.

Format:
answer_1
answer_2
...

sample

3 2
1 2 3
2 3 1 4
1 1 2 2

52
33

</p>