막대 위의 개미들

Ada에게는 $1$부터 $\mathbf{N}$까지의 표지가 붙은 개미 $\mathbf{N}$마리가 있다. Ada는 John의 집중력을 시험하기로 한다. Ada는 길이가 $\mathbf{L}$ cm인 막대를 가져와 그 위에 개미들을 떨어뜨린다.

개미를 떨어뜨린 막대 위의 위치는 정수 배열 $\mathbf{P}$로 나타내며, 개미 $i$는 막대 위의 위치 $\mathbf{P_i}$, 즉 왼쪽 끝에서 $\mathbf{P_i}$ cm 떨어진 곳에 떨어진다. 각 개미는 초당 $1$ cm의 일정한 속력으로 왼쪽 또는 오른쪽으로 이동한다. 개미들의 초기 방향은 배열 $\mathbf{D}$로 나타내며, 개미 $i$의 방향은 $\mathbf{D_i}$이다. 왼쪽이면 $0$, 오른쪽이면 $1$이다. 두 개미가 만나면 서로 튕겨 나가 방향을 반대로 바꾼다. 개미들은 막대의 어느 한쪽 끝에 도달하면 막대에서 떨어진다.

Ada는 개미들이 막대에서 떨어지는 정확한 순서를 찾으라고 John에게 도전한다. John에게는 당신의 도움이 필요하다!

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{N} \lt \mathbf{L}$. 모든 $i$에 대해 $\mathbf{D_i} \in \{0, 1\}$. 모든 $i$에 대해 $0 \lt \mathbf{P_i} \lt \mathbf{L}$. 모든 $\mathbf{P_i}$는 서로 다르다.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 10$. $1 \le \mathbf{L} \le 100$.

테스트 세트 2

시간 제한: 40초. $1 \le \mathbf{N} \le 10^3$. $1 \le \mathbf{L} \le 10^9$.

테스트 세트 3

시간 제한: 40초. $1 \le \mathbf{L} \le 10^9$. 최대 15개의 케이스에 대해: $1 \le \mathbf{N} \le 10^5$. 나머지 케이스에 대해: $1 \le \mathbf{N} \le 10^3$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 $\mathbf{N}$와 $\mathbf{L}$이 주어지며, 각각 개미의 수와 막대의 길이를 나타낸다. 다음 $\mathbf{N}$개 줄에는 개미들의 위치와 방향이 주어진다. $i$-번째 줄에는 두 정수 $\mathbf{P_i}$과 $\mathbf{D_i}$가 주어지며, 각각 개미 $i$의 위치와 방향을 나타낸다.

각 테스트 케이스마다 Case #$x$: $A_1 A_2 \dots A_N$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $A_i$는 막대에서 떨어지는 $i$-번째 개미의 표지이다. 다시 말해, 막대에서 가장 먼저 떨어지는 개미는 표지가 $A_1$인 개미이고, 두 번째는 표지가 $A_2$인 개미이며, 이런 식으로 이어진다. 여러 개미가 동시에 떨어지면 그 표지를 오름차순으로 출력한다.

샘플 케이스 #1에서는 표지가 $1$인 개미 한 마리만 있으므로, 이 개미만 떨어진다. 이 개미가 떨어지는 시각은 $4$초이다.

샘플 케이스 #2에서 두 개미는 서로를 향해 이동하여 $0.5$초에 만나고 방향을 반대로 바꾼다. 그 후 개미 $2$은 $3$초에 막대의 오른쪽 끝에 도달하는 반면, 개미 $1$은 $5$초에 왼쪽 끝에 도달한다. 따라서 개미 $2$가 막대에서 떨어지고, 이어서 개미 $1$가 떨어진다.

샘플 케이스 #3에서 개미 $2$와 $4$는 서로를 향해 이동하여 $1$초에 만난다. 마찬가지로 개미 $1$와 $3$도 서로를 향해 이동하여 $1$초에 만난다. 그러면 개미 $4$마리 모두 방향을 바꾼다.

• 개미 $1$와 $2$는 막대의 서로 반대쪽 끝을 향해 이동하여 $4$초에 떨어진다.

• 개미 $3$와 $4$는 서로를 향해 이동하여 $3$초에 만난다. 이들은 방향을 바꾸어 막대의 서로 반대쪽 끝을 향해 이동하고, $8$초에 떨어진다.