The court wizard Zigzag wants to become a famous mathematician. For that, he needs his own theorem, like the Cauchy theorem, or his sum, like the Minkowski sum. But most of all he wants to have his sequence, like the Fibonacci sequence, and his function, like the Euler's totient function.

The Zigag's sequence with the zigzag factor z is an infinite sequence Siz (i ≥ 1; z ≥ 2), that is determined as follows:

  * Siz = 2, when <image>; 
  * <image>, when <image>; 
  * <image>, when <image>. 



Operation <image> means taking the remainder from dividing number x by number y. For example, the beginning of sequence Si3 (zigzag factor 3) looks as follows: 1, 2, 3, 2, 1, 2, 3, 2, 1.

Let's assume that we are given an array a, consisting of n integers. Let's define element number i (1 ≤ i ≤ n) of the array as ai. The Zigzag function is function <image>, where l, r, z satisfy the inequalities 1 ≤ l ≤ r ≤ n, z ≥ 2.

To become better acquainted with the Zigzag sequence and the Zigzag function, the wizard offers you to implement the following operations on the given array a.

  1. The assignment operation. The operation parameters are (p, v). The operation denotes assigning value v to the p-th array element. After the operation is applied, the value of the array element ap equals v. 
  2. The Zigzag operation. The operation parameters are (l, r, z). The operation denotes calculating the Zigzag function Z(l, r, z). 



Explore the magical powers of zigzags, implement the described operations.

Input

The first line contains integer n (1 ≤ n ≤ 105) — The number of elements in array a. The second line contains n space-separated integers: a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array. 

The third line contains integer m (1 ≤ m ≤ 105) — the number of operations. Next m lines contain the operations' descriptions. An operation's description starts with integer ti (1 ≤ ti ≤ 2) — the operation type. 

  * If ti = 1 (assignment operation), then on the line follow two space-separated integers: pi, vi (1 ≤ pi ≤ n; 1 ≤ vi ≤ 109) — the parameters of the assigning operation. 
  * If ti = 2 (Zigzag operation), then on the line follow three space-separated integers: li, ri, zi (1 ≤ li ≤ ri ≤ n; 2 ≤ zi ≤ 6) — the parameters of the Zigzag operation. 



You should execute the operations in the order, in which they are given in the input.

Output

For each Zigzag operation print the calculated value of the Zigzag function on a single line. Print the values for Zigzag functions in the order, in which they are given in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Examples

Input

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


Output

5
26
38

Note

Explanation of the sample test: 

  * Result of the first operation is Z(2, 3, 2) = 3·1 + 1·2 = 5. 
  * Result of the second operation is Z(1, 5, 3) = 2·1 + 3·2 + 1·3 + 5·2 + 5·1 = 26. 
  * After the third operation array a is equal to 2, 3, 5, 5, 5. 
  * Result of the forth operation is Z(1, 5, 3) = 2·1 + 3·2 + 5·3 + 5·2 + 5·1 = 38. 
5
42665793 142698407 856080769 176604645 248258165
10
1 5 141156007
2 5 5 3
2 4 4 2
2 2 5 3
1 2 942795810
2 5 5 3
1 3 195194439
1 2 698674322
1 2 602158126
2 2 4 2
 5
259349921 585246931 574682827 407653643 902894459
10
2 3 5 5
1 3 578806357
2 2 3 5
1 5 556830122
1 3 542486819
2 4 4 5
1 2 650599782
2 1 5 2
2 2 4 2
1 4 384265705
 5
798491505 143876925 714252070 70903672 75576312
10
1 4 894875534
1 2 547197376
1 4 190083985
2 2 5 3
1 5 882369084
1 4 257095083
2 4 5 6
1 5 313038735
1 5 338812312
2 4 4 2
 5
581807377 848812048 848166364 134821971 713647858
10
2 2 3 5
2 5 5 5
2 5 5 2
1 1 467786083
2 4 5 5
1 3 232276328
1 5 146097986
2 1 5 6
2 5 5 3
1 3 143011686

141156007
176604645
2666985894
141156007
1169151649
 4098673490
1742859645
407653643
3475173712
2143227063
 2697106095
2021833251
257095083
 2545144776
713647858
713647858
1562117687
4132016977
146097986

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <functional>
#include <cmath>

#if !defined(__GNUC__)
#include <hash_set>
#include <hash_map>

typedef signed char int8_t;
typedef unsigned char uint8_t;
typedef signed short int16_t;
typedef unsigned short uint16_t;
typedef signed long int32_t;
typedef unsigned long uint32_t;
typedef signed long long int64_t;
typedef unsigned long long uint64_t;

typedef stdext::hash_set<size_t>    hash_set_size_t;
#else // !defined(__GNUC__)

#endif // !defined(__GNUC__)

typedef long double double_t;
typedef std::string string8_t;

typedef std::vector<size_t> vector_size_t;
typedef std::vector<int32_t> vector_int32_t;
typedef std::vector<uint32_t> vector_uint32_t;
typedef std::vector<uint64_t> vector_uint64_t;
typedef std::vector<vector_uint64_t> vector_2d_uint64_t;
typedef std::set<size_t> set_size_t;
typedef std::multiset<size_t> multiset_size_t;

typedef std::vector<string8_t> vector_string8_t;
typedef std::set<string8_t> set_string8_t;
typedef std::multiset<std::string> multiset_string8_t;

// Auxiliary functions definition
// 
template<typename T> inline T Abs(const T a) { return a < 0 ? -a : a; }
template<typename T> inline T Min(const T a, const T b) {return a < b ? a : b;}
template<typename T> inline T Max(const T a, const T b) {return a > b ? a : b;}
template<typename T> inline void UpdateMin(T& a, const T b) {a = Min(a, b);}
template<typename T> inline void UpdateMax(T& a, const T b) {a = Max(a, b);}

static const double_t eps = 1.0e-09;
template<typename T> inline bool IsEqual(const T a, const T b) { return Abs(a - b) < eps; }
template<typename T> inline bool IsGreater(const T a, const T b) { return a > b + eps; }
template<typename T> inline bool IsLess(const T a, const T b) { return a + eps < b; }

template<typename T> inline string8_t ToStr(const T& val) { std::ostringstream ostr; ostr << val; return ostr.str(); }
template<typename T> inline bool FromStr(const string8_t& str, T& val) {std::istringstream istr(str); istr >> val; return !!istr; }

template<typename T> inline std::istream& operator>>(std::istream& ist, std::vector<T>& data)
{
    for (size_t i = 0; i < data.size(); i++) { ist >> data[i]; }
    return ist;
}

#if defined(ONLINE_JUDGE) || defined(__GNUC__)
template<size_t id> class StopWatch { };
#else //defined(ONLINE_JUDGE)
#include <library/lib_stopwatch.h>
#endif //defined(ONLINE_JUDGE)

class NonCopyable
{
protected:
    NonCopyable() {}
    ~NonCopyable() {}
private:
    NonCopyable& operator=(const NonCopyable&);
    NonCopyable(const NonCopyable&);
};

template<typename ValueType>
struct ICombineFunction : public std::binary_function<ValueType, ValueType, ValueType>
{
    typedef ValueType value_type_t;
    virtual value_type_t operator()(const value_type_t& l, const value_type_t& r) const = 0;
    virtual value_type_t GetDefaultValue() const = 0;
    virtual ~ICombineFunction() {}
};

template<typename value_type_t>
class SegmentTree : public NonCopyable
{
public:
    typedef std::vector<value_type_t> values_t;
    typedef ICombineFunction<value_type_t> combine_function_t;

    explicit SegmentTree(const values_t& inputData, combine_function_t* funcPtr)
        : m_funcPtr(funcPtr), m_func(*m_funcPtr), m_defaultValue(m_func.GetDefaultValue())
    {
        Preprocess(inputData);
    }

    // [idxBegin, idxEnd)
    value_type_t CalculateForRange(size_t idxBegin, size_t idxEnd) const
    {
        if (idxBegin == idxEnd)
            return m_defaultValue;

        const size_t len = m_resultTree[0].size();
        const size_t curPow = m_resultTree.size()-1;
        return CalculateForRangeRecPart(0, len, curPow, idxBegin, idxEnd);
    }

    void UpdateValue(const size_t idx, const value_type_t& val)
    {
        UpdateTreeAfterValueUpdate(idx, val);
    }

private:
    typedef std::vector<values_t> combined_result_tree_t;

    value_type_t CalculateForRangeRecPart(size_t disp, size_t len, size_t curPow2, size_t idxBegin, size_t idxEnd) const
    {
        // "len" is current power of 2
        const size_t l = disp;
        const size_t r = disp + len;

        if (curPow2 == 0)
        {
            return m_resultTree[curPow2][disp];
        }

        if (l == idxBegin && r == idxEnd)
        {
            return m_resultTree[curPow2][disp / len];
        }

        const size_t mid = disp + len / 2;

        if (mid <= idxBegin)
        {
            return CalculateForRangeRecPart(mid, len / 2, curPow2 - 1, idxBegin, idxEnd);
        }
        else if (mid >= idxEnd)
        {
            return CalculateForRangeRecPart(disp, len / 2, curPow2 - 1, idxBegin, idxEnd);
        }
        else
        {
            const value_type_t v1 = CalculateForRangeRecPart(disp, len / 2, curPow2 - 1, idxBegin, mid);
            const value_type_t v2 = CalculateForRangeRecPart(mid, len / 2, curPow2 - 1, mid, idxEnd);
            return m_func(v1, v2);
        }
    }

    void Preprocess(const values_t& inputData)
    {
        const size_t n = inputData.size();

        size_t upperPow2 = 1;
        while (upperPow2 < n) {upperPow2 *= 2;}

        m_resultTree.push_back(inputData);
        m_resultTree[0].resize(upperPow2);
        std::fill(m_resultTree[0].begin() + inputData.size(), m_resultTree[0].end(), m_defaultValue);

        size_t pow2 = 1;
        size_t multiplier = 2;

        while (multiplier <= upperPow2)
        {
            const size_t lineSize = upperPow2 / multiplier;
            const values_t& prevLine = m_resultTree[pow2-1];
            values_t nextLine(lineSize, m_defaultValue);

            for (size_t i = 0; i < lineSize; i++)
                nextLine[i] = m_func(prevLine[2*i], prevLine[2*i + 1]);

            m_resultTree.push_back(nextLine);

            pow2 += 1;
            multiplier *= 2;
        }
    }

    void UpdateTreeAfterValueUpdate(const size_t updatedValueIdx, const value_type_t updatedValue)
    {
        const size_t n = m_resultTree[0].size();
        // TODO: common assert func
        if (updatedValueIdx >= n)
            _CrtDbgBreak();

        m_resultTree[0][updatedValueIdx] = updatedValue;

        size_t pow2 = 1;
        size_t currentIdx = updatedValueIdx / 2;

        while (pow2 < m_resultTree.size())
        {
            m_resultTree[pow2][currentIdx] = m_func(
                m_resultTree[pow2 - 1][2 * currentIdx], 
                m_resultTree[pow2 - 1][2 * currentIdx + 1]);

            pow2 += 1;
            currentIdx /= 2;
        }
    }

    const std::auto_ptr<const combine_function_t> m_funcPtr;
    const combine_function_t& m_func;
    const value_type_t m_defaultValue;
    combined_result_tree_t m_resultTree;
};

struct SumUInt64 : ICombineFunction<uint64_t>
{
    uint64_t operator()(const uint64_t& l, const uint64_t& r) const
    {
        return l + r;
    }

    uint64_t GetDefaultValue() const
    {
        return 0;
    }
};



vector_uint64_t GetZFunc(const size_t n, const uint32_t z)
{
    const uint32_t mod = 2*z - 2;
    vector_uint64_t r(n);
    for (size_t i = 1; i <= n; i++)
    {
        const uint32_t m = (uint32_t)(i % mod);
        if (m == 0)
            r[i - 1] = 2;
        else if (m <= z)
            r[i - 1] = m;
        else 
            r[i - 1] = 2 * z - m;
    }
    return r;
}

uint64_t GetSum(const vector_uint64_t& a, const size_t l, const size_t r, const vector_uint64_t& f)
{
    uint64_t s = 0;
    for (size_t i = l; i <= r; i++)
    {
        s += (uint64_t)a[i] * f[i - l];
    }
    return s;
}

const uint32_t MinZ = 2;
const uint32_t MaxZ = 6;
const size_t TailSize = MaxZ * 2 - 2;

struct TreeHolder
{
    typedef SegmentTree<uint64_t> Tree64;
    typedef Tree64* Tree64Ptr;
    typedef std::vector<Tree64Ptr> TreeVector;
    typedef std::vector<TreeVector> TreeVector2d;

    static size_t GetDxMod(const size_t z)
    {
        return 2 * z - 2;
    }

    TreeHolder(const vector_uint64_t& a)
    {
        const size_t n = a.size();

        zf.resize(MaxZ - 1);
        for (uint32_t z = MinZ; z <= MaxZ; z++)
            zf[z - MinZ] = GetZFunc(n + TailSize, z);

        for (uint32_t z = MinZ; z <= MaxZ; z++)
        {
            TreeVector tree;
            for (uint32_t dx = 0; dx < GetDxMod(z); dx++)
            {
                vector_uint64_t x(a);
                for (size_t i = 0; i < n; i++)
                    x[i] *= zf[z - MinZ][i + GetDxMod(z) - dx];

                tree.push_back(new Tree64(x, new SumUInt64()));
            }
            trees.push_back(tree);
        }
    }

    uint64_t GetValue(const size_t l, const size_t r, const size_t z)
    {
        const Tree64& tree = *trees[z - MinZ][l % GetDxMod(z)];
        const uint64_t val = tree.CalculateForRange(l, r);
        return val;
    }

    void UpdateValue(const size_t idx, const uint64_t val)
    {
        for (uint32_t z = MinZ; z <= MaxZ; z++)
        {
            for (uint32_t dx = 0; dx < GetDxMod(z); dx++)
            {
                trees[z - MinZ][dx]->UpdateValue(idx, val);
            }
        }
    }

    ~TreeHolder()
    {
        for(size_t i = 0; i < trees.size(); i++)
        {
            for (size_t j = 0; j < trees[i].size(); j++)
            {
                delete trees[i][j];
            }
        }
        trees.clear();
    }

    vector_2d_uint64_t zf;
    TreeVector2d trees; 
};

void TestTreeHolder()
{
    const size_t n = 16;
    const uint64_t initialValue = 1;
    const uint64_t newValue = 11;

    vector_2d_uint64_t zf(MaxZ - 1);
    for (uint32_t z = MinZ; z <= MaxZ; z++)
        zf[z - MinZ] = GetZFunc(n + TailSize, z);

    vector_uint64_t a(n, initialValue);
    TreeHolder trees(a);

    for (size_t i = 0; i <= n; i++)
    {
        if (i != 0)
        {
            a[i - 1] = newValue;
            trees.UpdateValue(i - 1, newValue);
        }
        for (size_t l = 0; l < n; l++)
        {
            for (uint32_t z = MinZ; z <= MaxZ; z++)
            {
                const uint64_t sum = trees.GetValue(l, l + 1, z);
                const uint64_t expectedSum = a[l];
                if (sum != expectedSum)
                    _CrtDbgBreak();
            }
        }
    }
}

bool Solve(std::istream& ist, std::ostream& ost, const bool multipleTestMode)
{
    StopWatch<1> sw;

    // first input value
    size_t n;
    ist >> n;

    if (multipleTestMode && !ist)
        return false;

    vector_uint64_t a(n);
    ist >> a;

    // remain input & solve
    TreeHolder trees(a);

    vector_2d_uint64_t zf(MaxZ - 1);
    for (uint32_t z = MinZ; z <= MaxZ; z++)
        zf[z - MinZ] = GetZFunc(n + TailSize, z);

    size_t m;
    ist >> m;
    for (size_t i = 0; i < m; i++)
    {
        uint32_t t;
        ist >> t;
        if (t == 1)
        {
            size_t p;
            uint32_t v;
            ist >> p >> v;
            trees.UpdateValue(p - 1, v);
        }
        else
        {
            size_t l, r;
            uint32_t z;
            ist >> l >> r >> z;

            const uint64_t sum = trees.GetValue(l - 1, r, z);
            ost << sum << std::endl;
        }
    }

    return multipleTestMode;
}

int main()
{
    //TestTreeHolder();
    //return 0;

    std::ios_base::sync_with_stdio(false);
    std::istream& ist = std::cin;
    std::ostream& ost = std::cout;
#if defined(ONLINE_JUDGE)
    Solve(ist, ost, false);
#else
    while(Solve(ist, ost, true)) {};
#endif
}
