IOPC1207 - GM plants

The latest attraction for Techkriti 2112 is is a huge display of genetically modified plants. The arrangement consists of a cuboidal box of size Nx × Ny × Nz made of unit cubes. Each unit cube is identified using (x, y, z) coordinates - x ranges from 0 to Nx-1 and so on - and contains a plant genetically modified to show fluorescence. The natural colour of the plants is green. However, on exposing a plant to laser light, it changes colour to red. What is more interesting is that on exposing a red plant to laser light again, it changes back to green and this continues.

The organisers have realised that they can use the display to make many coloured patterns. They have with them a laser light sheet which they can place along an axis and move in one direction, exposing many plants to light at once. For example, if the plane of the light sheet is kept as the y axis and it is moved from a to b, every plant with the y coordinate between a and b inclusive will turn from green to red or red to green. Every time the laser is operated, it is only the plants with one specific coordinate in a certain range which are affected.

You are told that initially all plants were green. Given the sequence of exposing plants to laser light, your task is to find the number of red coloured plants in certain cuboidal subregions of the display

Input

The first line of the input contains T, the number of test cases (T ≤ 10). Following this are the descriptions of the T test cases. The description of each test case starts with a line containing four space separated integers : Nx, Ny, Nz and Q (1 ≤ Nx, Ny, Nz ≤ 100000; Q ≤ 5000). The first three are the extents of the display in the three dimensions while Q is the number of queries which are to follow. Following this are Q lines, each describing a query. A query will be of one of the following forms :

  • 0 i j : expose all plants with x coordinates i ≤ x ≤ j to laser light
  • 1 i j : expose all plants with y coordinates i ≤ y ≤ j to laser light
  • 2 i j : expose all plants with z coordinates i ≤ z ≤ j to laser light
  • 3 x1 y1 z1 x2 y2 z2 : Report the number of red plants in the cuboidal region with (x1,y1,z1) and (x2,y2,z2) as diagonally opposite cells - ie, all red plants with x1 ≤ x ≤ x2, y1 ≤ y ≤ y2 and z1 ≤ z ≤ z2

All individual coordinates will be valid - i.e, every x coordinate will be such that 0 ≤ x ≤ Nx-1 and so on. Also, i ≤ j; x1 ≤ x2; y1 ≤ y2 and z1 ≤ z2

Output

For every query of the form 3 x1 y1 z1 x2 y2 z2 in the input, output the number of red plants with coordinates constrained by x1 ≤ x ≤ x2, y1 ≤ y ≤ y2 and z1 ≤ z ≤ z2

Example

Input:
1
3 4 5 5
0 1 2
1 2 3
3 0 0 0 1 2 3
2 3 4
3 1 1 1 2 2 2

Output:
12
4

Added by:Raziman T V
Date:2012-01-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:http://www.codechef.com/IOPC2012/

hide comments
2015-12-17 15:53:11 Shivam Mitra
How is the answer 12 for first query?
2015-07-12 08:32:43 anando_du
finally AC !!
1. use segtree (without building , just update it)
2. use long long int (this caused me 4 WA within 6 submission)
2014-03-23 23:27:03 zicowa
do not try to buildthe tree simple update it for the red count otherwise you will get TLe use lazy propagation
2013-08-31 12:07:20 npsabari
Careful observation is needed to get the formula!
2013-06-22 11:55:54 karan173
same here tle on 8th run. please see admins
2013-04-11 22:29:34 Akshat
I don't understand why my code is failing. Is it a corner case?
2013-03-01 13:17:37 foram
getting TLE in 8th run, even after using lazy propagation!!

Last edit: 2013-03-01 13:18:11
2012-12-28 21:01:16 Harish Vishwakarma
Got six SIGSEGV error till now. The code is running fine on Ideone for the given input. Requesting the admin to please check the code and suggest corrections.

Answer : You are trying to make an array with 10^15 elements. You need to rethink your algo.

Last edit: 2013-01-02 06:17:22
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.