Corpuscle Laboratory

HUST Past Monthly Hard Problems Challenge Contest (1)

Time Limit : 15 Second

Memory Limit : 128 MB

Submission: 70

Solved: 13

Description

As one of the world's top laboratory, Corpuscle Laboratory has the most developed decetors. Each detector can keep watch on a specific varible of every corpuscles in the experimential container(e.g mass, volume, temperature, color(in R, G, B) and so on).
One day, Katrina needs to do a series of experiments in Corpuscle Lab, the first step of each experiment is to control the amount of some corpuscles with specific conditions. All the n varibles in the experiments are discrete and independent, which means that all the varibles can be treated as integers from 0 to m-1(m means the degree of freedom of a varible here) and varible a has nothing to do which varible b. At the beginning, on every possible state, there is one corpuscle.
A state [x] is a n-dimension vector (x1, x2, ..., xn), x1, x2, ..., xn are varibles that describe corpuscles. For example, an experiment use 3 varibles to describe corpuscles, like (x-coordinate, y-coordinate, z-coordinate), then state [s] = (3, 2, 3) specifies a position in 3-dimension space. If there are 3 corpuscles at position (3, 2, 3), we say "there are 3 corpuscles at [s]".
Things are more complicated here, the experiments use not only the position of a corpuscles to descirbe it, but also other varibles, like mass and volume. A state [x] = (x, y, z, t, m), x, y, z describe the position of corpuscles, t is refer to temperature and m is refer to mass. Then (1, 2, 3, 30, 1) refers to corpuscles at position (1, 2, 3), and their temperature and mass is 30 and 1.
As chief programmer of the Lab, you are required to write a program that can offer her the data of the amount of corpuscles in a certain RANGE(You'll see what RANGE means here later), so that she can use other equipments in the Lab to handle the corpuscles.
In order to finish this jop, you have to deal with 2 kinds of opoerations:
First: Q [u] [v]
A query of the amount of corpuscles in the RANGE {(x1, x2, ..., xn) | ui <= xi <= vi, 1 <= i <= n}. [u] and [v] are n dimension vector like (d1,d2, ..., dn), and d1, d2, ..., dn are the n varibles.
Second: C [u] [v] k
Change k corpuscles from state [u] to state [v].

Input

The input contains several test cases. Each test cases consist of 3 parts:
First, Line 1: 2 integers, n and q(1 <= n <= 6, 0 <= q <= 1000), the number of varibles and number of operations;
Second, Line 2: n integers m1, m2, ..., mn(m1 * m2 * ... * mn <= 2^24), here mi is the degree of the freedom of varible i;
Third, Line 3 ~ q+2: each line contains one operation in the form, Q u1 u2 ... un v1 v2 ... vn, or C u1 u2 ... un v1 v2 ... vn k.
The input guarantees that all the operations are legal.

Output

Just answer all the Q query, one per line.

sample input

sample output

hint

source

Zhang l

Submit