Description

Kobayashi is a programmer, and naturally Kanna becomes very interested in this human “magic,” so Kobayashi starts teaching her OI.

Today Kanna learned a magical structure called a segment tree, which can maintain information over an interval and is very powerful. Kanna tried to write a segment tree that maintains the sum over intervals. Since she doesn’t know how to use lazy propagation, she performs each range add operation by brute-force point updates. The specific code is as follows:

struct Segment_Tree{
#define lson (o<<1)
#define rson (o<<1|1)
    int sumv[N<<2],minv[N<<2];
    inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];}
    inline void build(int o,int l,int r){
        if(l==r){sumv[o]=a[l];return;}
        int mid=(l+r)>>1;
        build(lson,l,mid);build(rson,mid+1,r);
        pushup(o);
    }
    inline void change(int o,int l,int r,int q,int v){
        if(l==r){sumv[o]+=v;return;}
        int mid=(l+r)>>1;
        if(q<=mid)change(lson,l,mid,q,v);
        else change(rson,mid+1,r,q,v);
        pushup(o);
    }
}T; 

When modifying, she writes:

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

Obviously, each node of this segment tree stores the sum of the interval it governs.

Kanna is thoughtful, and she suddenly came up with a question:

After each range add operation on the segment tree is completed, starting from the root, at each internal node choose one child with equal probability and continue until reaching a leaf node. Sum the values of all nodes along the path. What is the expected value of this sum?

Each time, Kanna will give you a value $qwq$, and it is guaranteed that the expected value multiplied by $qwq$ is an integer.

This problem is so easy that clever Kanna solved it in an instant.

Now she wonders, can you solve it too?

Input Format

The first line contains integers $n, m, qwq$, which denote the length of the original sequence, the number of operations, and the denominator used for output.

The second line contains $n$ integers, the original sequence.

The next $m$ lines each contain three integers $l, r, x$, meaning add $x$ to the interval $[l, r]$.

Output Format

Output $m$ lines. Each line is the expected path-sum value multiplied by $qwq$.

8 2 1
1 2 3 4 5 6 7 8
1 3 4
1 8 2

90
120

Hint

Constraints:

• For 30% of the testdata, $1 \leq n, m \leq 100$.
• For 70% of the testdata, $1 \leq n, m \leq 10^{5}$.
• For 100% of the testdata, $1 \leq n, m \leq 10^{6}$.
• $-1000 \leq a_i, x \leq 1000$.

Translated by ChatGPT 5