REQ problem in python

Time limit: 15 seconds

Memory limit: 256 Mb

REQ(l, r, k) is number of times value k occurs in range [l, r):

You have initial array a of 0 < N 100000 elements and 0 < M 100000 queries of two types:

? l r k REQ(l, r, k)

or

+ i delta inc(i, delta): increase a[i] value by delta.

It is guaranteed that elements of array never exceed K: 0 a_i K.

Input format

First line contains 3 integer numbers: 0 < N, M 100000; 0 < K 100 number of items in array, number of queries and limitation on values in array.

Next line contains N integer numbers values of initial array a: 0 a_i K.

Each of next M lines contains character followed by 3 or 4 integer numbers request of one of two types:

? l r k REQ(l, r, k): 0 l < r N; 0 k K

or

+ i delta inc(i, delta): increase a[i] value by delta. 0 i < N; -K k K

Output format

For each "?" query provide answer for REQ request.

Sample 1

Input	Output
2 8 1 0 0 ? 0 2 0 ? 0 2 1 + 0 1 ? 0 2 0 ? 0 2 1 + 1 1 ? 0 2 0 ? 0 2 1	2 0 1 1 0 2

Sample 2

Input	Output
3 7 10 1 1 1 ? 0 3 1 + 1 2 ? 0 3 1 + 1 -1 ? 0 3 1 + 1 -1 ? 0 3 1	3 2 2 3

Sample 3

Input	Output
10 10 10 0 3 1 0 9 9 7 0 6 4 ? 0 10 1 ? 0 7 4 + 2 3 ? 1 10 1 ? 2 5 4 ? 1 4 0 ? 1 10 2 + 3 2 ? 0 4 0 ? 0 7 2	1 0 0 1 1 0 1 1