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.

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.

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.

生化危机

（Time：2s，Memory：512Mb）

题目大意：

布雷拉（Umbrella）公司又开发了新的生化病毒，里昂在无意之间发现了布雷拉公司的阴谋。不过在他逃跑的过程中被布雷拉公司发现了，布雷拉公司在城市中释放生化兽以阻止里昂寻找到证据。里昂所在的城市是一个n*n的大小的正方形区域。布雷拉公司有50种生化兽，布雷拉公司每次释放生化兽前都会指定释放生化兽的种类及数量，在指定的矩形区间内的每个单位区域释放指定种类及数量的生化兽。比如指定释放的区域为左上角为（1,1），右下角为（3,3）的区域，指定的种类和数量为A类3只，B类2只，C类1只，那么在指定的区间内每个单位面积都有A类生化兽3只，B类生化兽2只，C类生化兽1只。里昂为了搜集证据必须探索指定的区域，在探索区域的时候会将区域内的所有生化兽吸引到里昂身边，里昂在处理相同种类的生化兽的时候有两种处理方法，如果为偶数这进行躲避，如果是奇数就全部击杀。但是里昂不太精通数学，为了使行动更顺利想提前知道每种生化兽的处理方法，你可以帮助他吗？

输入：

初始的时候城市里没有生化兽

先输入n，m（1<=n<=3000 1<=m<=100000）分别代表城市大小和操作数量

接下来m行分别为各种操作

P 操作是进行投放生化兽 x1,y1,x2,y2(1<=x1,y1,x2,y2<=n) 代表投放区域的左上角和右下角 之后紧接着数字k代表投放生化兽的次数，之后紧接着k对数字 （a ，b）， a(1<=a<=50)代表生化兽的种类 b(1<=b<=100000)代表投放生化兽的数量。

Q 操作是查询操作 x1,y1,x2,y2代表查询区间的左上角和右下角

输出：

根据每个查询输出50个数字 分别代表对于第k类生化兽采取的行动方式 1代表躲藏 2代表全部击杀