Resident Evil

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

Description

The Umbrella Company has developed a new biochemical virus secretly. Lyon, a staff of the company, happened to find out the conspiracy and his company is now stopping him from discovering further evidence by releasing biochemical monster in his city (don’t ask me why the company is using this weird method).

The city can be described as an n*n grids. The Umbrella Company has 50 kinds of biochemical monster in total. The company will specify the type, quantity of biochemical monster and the rectangle area to put monster. For example, if the specified rectangle area has upper left corner (1, 1) and bottom right corner of (3, 3), and the company wishes to put 3 of A monster, 2 of B monster and 1 of C monster in it, then 3 of A monster, 2 of B monster and 1 of C monster is added to each and every grid inside the area.

However, Lyon risk his life of finding evidence by searching certain rectangle area. By doing this, all monsters inside the area would gather to him. He has two way of dealing with monster. If the number of a certain kind of monster is even, then he would choose to hide, otherwise withdraw.

Input

A line containing n and m (1<=n<=3000 1<=m<=100000). Representing the size of the city and the number of operations.

  Then m lines of operation and there are only two kinds of operation.

Letter ‘P’ means to release monster, followed by 4 integers x1, y1, x2, y2 (1<=x1, y1, x2, y2<=n) , describing the upper left corner and bottom right corner of the area. Then an integer K(1<=K<=50), meaning there will be k pair of number (A, B) given next. A (1<=A<=50) indicates the kind of the monster and B (1<=b<=100000) indicates the number of this kind being added to this area.

Letter ‘Q’ represents the query operation, followed by 4 integers x1, y1, x2, y2 (1<=x1, y1, x2, y2<=n), describing the upper left corner and bottom right corner of the area.

Output

For every ‘Q’ operation. Print 50 number in a line, meaning the kind of action he would take for different kinds of monsters. 1 represents hiding and 2 represents withdrawing.

Sample Input

2 2 P 1 1 2 2 1 1 1 Q 1 1 1 1

Sample Output

2 1 1 1 1 1 ........1 (one '2' and forty-nine '1')

Hint

wange2014

Source

2016 ACM/ICPC Asia Regional Shenyang Online

提交代码