Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P154SUMJ - ROUND 4J - Truy vấn

Cho mảng a[] gồm có n phần tử a[1], a[2], .., a[n].

Có 2 loại truy vấn như sau:

Loại 1: “0 L R x” – Gán tất cả các phần tử a[L], a[L + 1],…, a[R] bằng x

Loại 2: ”1 L R K” – Tính tổng a[i] * [(i – L + 1) ^ K] với L <= i <= R, và kết quả lấy dư cho BASE = 10^9 + 7 (Số K không âm và không quá 5).

Input

Dòng đầu tiên là gồm 2 số nguyên n , m(1 <= n, m <= 10^5), lần lượt là số phần tử của mảng và số truy vấn.

Dòng thứ hai chứa n số nguyên a[1], a[2], …, a[n] (0 <= a[i] <= 10^9).

m dòng tiếp theo chứa các truy vấn thuộc 2 dạng trên với các giá trị L, R, K, x thỏa mãn 1 <= L <= R <= 10^5, 0 <= x <= 10^9.

Output

Gồm nhiều dòng là kết quả của các truy vấn loại 2.

Example

Input:

10 10

6 4 1 8 7 10 3 5 1 5

0 2 3 1

0 1 3 0

1 2 5 3

1 8 8 5

1 1 4 5

0 4 9 1

0 5 9 1

1 3 3 4

0 1 6 9

1 5 9 5

Output:

664

5

8192

0

4689

Được gửi lên bởi:adm
Ngày:2015-07-24
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.