Problem B
Eating Chocolate

Olle and Lisa have received $N$ types of chocolate bars of various shapes from their parents, which they now plan to eat together (the chocolate bars, not the parents). Each chocolate bar is a rectangle consisting of $R_i \times C_i$ squares, and they have received $k_i$ identical copies of the $i$:th type. The chocolate bars are placed on a table, and to eat them, they take turns making the following move:

• Choose a chocolate bar from the table.

• Break it into two parts so that both parts are rectangles with integer side lengths.

• Eat the smaller part.

• Put the remaining larger part back on the table.

If the chosen chocolate bar has size $1 \times 1$, they eat it directly and do not place anything back on the table. They have already decided that Lisa will start.

Due to sibling affection, they will always choose a chocolate bar from the table that, after splitting it in two and placing the larger piece back, ensures that they eat as much as possible in that move. If there are multiple such choices, they arbitrarily select one. Additionally, Olle is very concerned about fairness and wants the total number of chocolate squares they eat to be as equal as possible. To achieve this goal, he may choose to throw away at most one chocolate bar in the trash before they begin, without Lisa noticing.

Let $V_O$ and $V_L$ be the number of squares that Olle and Lisa eat, respectively, given that they both eat in a gluttonous manner. Your task is to determine the minimum possible difference, i.e., $|V_O - V_L|$, after Olle has thrown away at most one chocolate bar.

Input

The first line contains the number $N$ ($1 \leq N \leq 10^5$), the number of chocolate bars on the table. Then follow $N$ lines, where the $i$-th line contains the numbers $R_i$, $C_i$, and $k_i$ ($1 \leq R_i, C_i \leq 10^6$, $1 \leq k_i \leq 10^9$), whose meaning is described above.

Output

Print an integer: the minimum value of $|V_O - V_L|$ as described above.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Sample 1

Olle throws away the chocolate bar of size $2 \times 2$. Then, they will each eat one square of chocolate twice, meaning $V_O = V_L$.

Explanation of Sample 2

In this test case, it is optimal for Olle not to throw away any chocolate bar. They will then eat exactly the same amount of chocolate.

3
1 2 1
2 2 1
2 1 1

0

1
1 1 4

0

3
4 7 1
8 8 1
4 1 1

10

4
12 34 1
13 37 2
20 25 3
1 101 4

94