Laser Beams
Contest: Kotlin Heroes: Episode 8
Difficulty rating: 2900
Tags: *special, geometry, probabilities

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 $$$Ox$$$ axis goes from left to right, and $$$Oy$$$ axis goes from bottom to top. A level is a rectangle with opposite corners in points $$$(0, 0)$$$ and $$$(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:

- basic enemies fire four laser rays in four directions: to the right (in the same direction as the vector $$$(1, 0)$$$), to the left (in the same direction as the vector $$$(-1, 0)$$$), up (in the same direction as the vector $$$(0, 1)$$$), and down (in the same direction as the vector $$$(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)$$$.

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.

The level Ira is working on has $$$n$$$ enemies. The $$$i$$$-th enemy is in the point $$$(x_i, y_i)$$$, and it has a probability of $$$p_i$$$ to be upgraded (it's either upgraded with probability $$$p_i$$$, or basic with probability $$$1-p_i$$$). 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 format:
The first line contains three integers $$$n$$$, $$$a$$$ and $$$b$$$ ($$$1 \le n \le 100$$$; $$$2 \le a, b \le 100$$$) — the number of enemies in the level and the dimensions of the level.

Then $$$n$$$ lines follow, the $$$i$$$-th of them contains three integers $$$x_i$$$, $$$y_i$$$ and $$$p'_i$$$ ($$$1 \le x_i \le a - 1$$$; $$$1 \le y_i \le b - 1$$$; $$$1 \le p'_i \le 999999$$$), meaning that the $$$i$$$-th enemy is located at $$$(x_i, y_i)$$$ and has a probability of $$$\frac{p'_i}{10^6}$$$ to be upgraded.

No two enemies are located in the same point.

Output format:
Print one integer — the expected number of parts in which the lasers divide the level, taken modulo $$$998244353$$$ (i. e. let the expected number of parts be $$$\frac{x}{y}$$$ as an irreducible fraction; you have to print $$$x \cdot y^{-1} \bmod 998244353$$$, where $$$y^{-1}$$$ is a number such that $$$y \cdot y^{-1} \bmod 998244353 = 1$$$).

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
Explanation to the first example:

With probability $$$\frac{1}{2}$$$, the only enemy is not upgraded and the level looks like this ($$$4$$$ parts):

With probability $$$\frac{1}{2}$$$, the only enemy is upgraded and the level looks like this ($$$8$$$ parts):

So, the expected number of parts is $$$4 \cdot \frac{1}{2} + 8 \cdot \frac{1}{2} = 6$$$.

Example input:
1 2 2
1 1 500000

Example output:
6

Example input:
2 3 2
1 1 500000
2 1 500000

Example output:
499122187

Editorial:
We will treat the level as a planar graph, where the segments of the rays and the level border denote the edges, and their intersection points denote the vertices. The main idea of the solution is to use Euler's Formula for planar graphs: for a connected planar graph, $$$f = e - v + 2$$$, where $$$e$$$ is the number of edges, $$$v$$$ is the number of vertices, and $$$f$$$ is the number of regions into which the graph divides the plane. The number of parts of the level is exactly $$$f - 1$$$ (since Euler's Formula treats the exterior as an additional region), and we will use the linearity of expectation to evaluate the expected value of the answer: $$$E(ans) = E(e) - E(v) + 1$$$.
Calculating $$$E(v)$$$ is easy. Firstly, let's generate all the intersection points between the rays and/or the borders in $$$O(n^2)$$$. Then, for each intersection point, calculate the probability of it being a part of the planar graph — which is the probability that at least one of the possible lines that pass through this point actually exists. For each of the four possible lines that can pass through the point, we can calculate the probability that it exists — and this allows us to easily calculate $$$E(v)$$$.
There are many different ways to find $$$E(e)$$$, but, in my opinion, the easiest one is to calculate the expected sum of degrees of all vertices (and the sum of degrees is exactly $$$2e$$$). For each vertex, if it is not the last vertex on some line, and this line exists, there is an edge to the next vertex on this line. Similarly, if it is not the first vertex on some line, and this line exists, there is an edge to the previous vertex on this line. So calculating the expected degree of a vertex is actually summing up the probabilities of existence of each line passing through it such that this vertex is not the first on that line, and adding the same values for the lines such that this vertex is not the last on that line (possibly counting the same line twice).
All that's left is to use the Euler's Formula to calculate $$$E(f)$$$.