P17572 [JAG 2026 Summer Camp #3] Ants Sort

Consider a line segment whose left and right endpoints are walls located at coordinates $0$ and $M$, respectively. The positive direction is to the right. There are $N$ ants on the line segment, numbered $1,2,\ldots,N$ from left to right. The $i$-th ant is initially located at coordinate $X_i$; thus, $0

The input consists of a single test case of the following format. ```text N M X_1 P_1 D_1 X_2 P_2 D_2 ... X_N P_N D_N ``` The first line contains two integers $N$ and $M$ ($2\le N\le 2\times10^5$, $6\le M\le10^{15}$, and $M$ is even), representing the number of ants and the coordinate of the right wall, respectively. For each $i$ ($1\le i\le N$), the $i$-th of the following $N$ lines contains two integers $X_i$ and $P_i$, and a character $D_i$, representing the initial coordinate of the $i$-th ant, the number of the ball it is initially carrying, and its initial direction, respectively. The coordinates $X_1,X_2,\ldots,X_N$ are even integers satisfying $0

Print the earliest time at which this goal can be achieved. It is guaranteed that the answer is an integer.