Dynamic Infinite Polynomial Maintenance

You are given an infinite polynomial

\(f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots\)

with all coefficients initially \(a_i=0\) for all \(i\ge0\). You need to support the following four types of operations:

1. Multiply Operation: Given integers L, R, v, multiply each coefficient \(a_i\) for \(L \le i \le R\) by v.
2. Add Operation: Given integers L, R, v, add v to each coefficient \(a_i\) for \(L \le i \le R\).
3. Shift Operation: Given integers L, R, multiply each term \(a_i x^{i}\) for \(L \le i \le R\) by \(x\) (i.e. shift that term one degree higher). Formally, for each \(i\) in \([L,R]\), remove \(a_i x^{i}\) and add it as \(a_i x^{i+1}\). Note that if an index already has a nonzero coefficient, the contributions are summed.
4. Evaluation Operation: Given an integer v, evaluate \(f(v)\) and output the result. The polynomial is not permanently modified by this operation (i.e. after evaluation, the polynomial reverts to its previous state). This operation is guaranteed to appear no more than 10 times.

Your task is to implement a program to perform a sequence of these operations.

inputFormat

The first line contains a single integer \(Q\) \( (1 \le Q)\) denoting the number of operations. Each of the following \(Q\) lines represents an operation in one of the following formats:

• For Multiply operation: 1 L R v
• For Add operation: 2 L R v
• For Shift operation: 3 L R
• For Evaluation operation: 4 v

It is guaranteed that all indices \(L, R\) and values given are integers and the operations are valid.

outputFormat

For each Evaluation operation (operation type 4), output a single line containing the value of \(f(v)\) evaluated at the given v.

sample

5
2 0 0 5
4 2
3 0 0
1 1 1 2
4 3

5
30