Laser Beams solution codechef

Laser Beams solution codechef

Ira is developing a computer game. This game features randomized generation and difficulty of levels. To achieve randomized difficulty, some enemies in each level are randomly replaced with stronger ones.

To describe how do the levels in the game look, let’s introduce a coordinate system in such a way that OxOx axis goes from left to right, and OyOy axis goes from bottom to top. A level is a rectangle with opposite corners in points (0,0)(0,0) and (a,b)(a,b). Each enemy’s position is a point in this rectangle.

As for now, Ira has implemented one type of enemy in the game, in two different versions — basic and upgraded. Both versions of enemies Ira has implemented fire laser rays in several directions:

Laser Beams solution codechef

  • basic enemies fire four laser rays in four directions: to the right (in the same direction as the vector (1,0)(1,0)), to the left (in the same direction as the vector (1,0)(−1,0)), up (in the same direction as the vector (0,1)(0,1)), and down (in the same direction as the vector (0,1)(0,−1));
  • upgraded enemies fire eight laser rays in eight directions: four directions listed for basic enemies, and four directions corresponding to vectors (1,1)(1,1)(1,1)(1,−1)(1,1)(−1,1)(1,1)(−1,−1).

Laser rays pass through enemies and are blocked only by the borders of the level (sides of the rectangle that denotes the level). Enemies are unaffected by lasers.

Laser Beams solution codechef

The level Ira is working on has nn enemies. The ii-th enemy is in the point (xi,yi)(xi,yi), and it has a probability of pipi to be upgraded (it’s either upgraded with probability pipi, or basic with probability 1pi1−pi). All these events are independent.

Ira wants to estimate the expected difficulty. She considers that a good way to evaluate the difficulty of the level is to count the number of parts in which the level is divided by the laser rays. So, she wants to calculate the expected number of these parts.

Help her to do the evaluation of the level!

Input Laser Beams solution codechef

The first line contains three integers nnaa and bb (1n1001≤n≤1002a,b1002≤a,b≤100) — the number of enemies in the level and the dimensions of the level.

Then nn lines follow, the ii-th of them contains three integers xixiyiyi and pipi′ (1xia11≤xi≤a−11yib11≤yi≤b−11pi9999991≤pi′≤999999), meaning that the ii-th enemy is located at (xi,yi)(xi,yi) and has a probability of pi106pi′106 to be upgraded.

No two enemies are located in the same point.

Output Laser Beams solution codechef

Print one integer — the expected number of parts in which the lasers divide the level, taken modulo 998244353998244353 (i. e. let the expected number of parts be xyxy as an irreducible fraction; you have to print xy1mod998244353x⋅y−1mod998244353, where y1y−1 is a number such that yy1mod998244353=1y⋅y−1mod998244353=1).

Examples
input

Copy Laser Beams solution codechef

1 2 2
1 1 500000
output

Copy Laser Beams solution codechef

6
input

Copy Laser Beams solution codechef

2 3 2
1 1 500000
2 1 500000
output

Copy Laser Beams solution codechef

499122187

Note Laser Beams solution codechef

Explanation to the first example:

With probability 1212, the only enemy is not upgraded and the level looks like this (44 parts):

Laser Beams solution codechef
With probability 1212, the only enemy is upgraded and the level looks like this (88 parts):

Laser Beams solution codechef
So, the expected number of parts is 412+812=64⋅12+8⋅12=6.

Leave a Reply

Your email address will not be published. Required fields are marked *

*