P17572 [JAG 2026 Summer Camp #3] Ants Sort

有一条线段，其左、右端点分别是位于坐标 $0$ 和 $M$ 处的墙壁。规定向右为正方向。 线段上有 $N$ 只蚂蚁，从左到右编号为 $1,2,\ldots,N$。第 $i$ 只蚂蚁最初位于坐标 $X_i$，因此有 $0

输入包含一组测试数据，格式如下。 ```text N M X_1 P_1 D_1 X_2 P_2 D_2 ... X_N P_N D_N ``` 第一行包含两个整数 $N$ 和 $M$（$2\le N\le2\times10^5$，$6\le M\le10^{15}$，且 $M$ 为偶数），分别表示蚂蚁的数量和右侧墙壁的坐标。 对于每个 $i$（$1\le i\le N$），接下来 $N$ 行中的第 $i$ 行包含两个整数 $X_i,P_i$ 和一个字符 $D_i$，分别表示第 $i$ 只蚂蚁的初始坐标、最初携带的球的编号，以及初始朝向。坐标 $X_1,X_2,\ldots,X_N$ 均为偶数，满足 $0

输出最早能够实现目标的时刻。保证答案为整数。