ICPC 2024 · Problem D · Doubles Horseback Wrestling

Time limit: 4 seconds

Horseback wrestling in Kyrgyzstan by Theklan Wikimedia Commons, CC BY-SA 4.0 The Nomadic Games Exploratory Committee (NGEC) is floating the idea of a doubles horseback wrestling tournament with pairs of riders astride single horses. They have advertised a pilot tournament, and $n$ eager riders have signed up to compete! So now the NGEC needs to pair the riders in order to make the tournament both fair and exciting.

The Central Asian Audaryspak League (CAAL) maintains a list of all horseback wrestlers and their ratings. From their previous expe- rience with ordinary horseback wrestling, the NGEC has decided that the pairs are best balanced if the ratings of their two riders add up to a particular integer, $s$.

For obscure licensing reasons, the CAAL refuses to release the exact rating of each rider. But the NGEC has some good estimates, knowing that any rider $i$’s true rating $r_{i}$ lies in an interval $[l_{i}, u_{i}]$. So the NGEC would consider pairing two riders $i$ and $j$ if there are ratings $ri \in [li, ui]$ and $rj \in [lj, uj]$ such that $ri+rj =s$.

The NGEC wants to form as many non-intersecting pairs of riders as possible. You need to help them.

Input

The first line contains two integers $n$ and $s$ ($2 \le n \le 2\cdot 10^{5}$, $1 \le s \le 10^{9}$), denoting the number of riders and the desired sum of ratings of riders in a pair. Riders are numbered 1 to $n$. This is followed by $n$ lines, where the $i$th line contains two integers $l_{i}$ and $u_{i}$ ($1\le li \le ui \le 10^{9}$), denoting the rating range of the $i$th rider.

Output

Output $k$, the maximum number of riding pairs that can be formed, followed by $k$ pairs of integers, denoting the numbers of the riders forming each pair. If there are multiple ways to pair off the riders, output any one.

Sample Input 1

6 10
6 7
1 4
2 2
3 8
5 7
9 9

Sample Output 1

2
6 2
3 4