21910_GreatWorldofGoo

The game is built around the idea of creating large structures using balls of goo. It is based on the prototype game Tower of Goo developed for Kyle Gabler's rapid game prototyping Experimental Gameplay Project. The game is divided into five chapters, each containing several levels. Each level has its own graphic and musical theme, giving it unique atmosphere, similar in style to Tim Burton's film designs. There is also a bonus meta-game called World of Goo Corporation, where the objective is to build the highest tower using goo balls which the player collected through the course of the game. Players from all over the world can compete, as the height of the tower and number of goo balls used are being constantly uploaded to the 2D Boy server.

-- Wikipedia

As mentioned above, World of Goo is an excellent independent game. Personally I like playing it rather than Plants vs. Zombies though both of them are great.

Let's consider a simplified version of "Fisty Bog" in Chapter One (Figure 1).

Figure 1

Ignore the part before the red line, as it's given by the system initially. The following goo balls make the bridge using regular triangles, numbered from 1, beginning from left to right. To ensure the bridge formed strictly horizontal, we place a light goo ball every three triangles, and in this problem we don't need to care about those balls.

From the figure we know that, some triangles are more danger during the construction process. For that case, goo balls want to be placed in different triangles. Risky goo balls want to be placed on the triangle more danger while others want safer ones. Now, my question comes, how many number of solutions exist when all goo balls are used and all wills are satisfied.

The first line: and integer k ( k ≤ 15 ) indicates the number of test case;

For each test case:

First line: n and m, 0 < m, n ≤ 500 , n represents the number of goo balls, m represents the number of wills;

Line 2…m+1:

Each line is consist of integers K  A₁  B₁  A₂  B₂  …  A_K  B_K  P  C₁  D₁  C₂  D₂  …  C_P  D_P, represents a restriction. That means the goo ball(s) numbered between A₁ and B₁ (inclusive), or between A₂ and B₂ (inclusive) or … or between A_K and B_K (inclusive) wants to be placed at triangle(s) number between C₁ and D₁ (inclusive), or between C₂ and D₂ (inclusive) or … or between C_P and D_P (inclusive). Two restrictions may be the same or partly same. Every restriction is legal.

For each test case, output one line with following rules.

Because in the world of goo, they only used 16bit system, which means the max number can be stored in one unit is 2¹⁶-1. So when the number of solutions exceeds 2¹⁶-1, we must output "OVERFLOW!", otherwise, output the accurate number of solutions.

3
6 1
1 1 6 1 1 4
6 1
1 1 6 1 1 3
10 1
1 1 10 1 1 8

720
0
OVERFLOW!