물리

매끄러운 수평 직선 트랙 위에 $n$개의 공이 있다. 트랙은 수직선으로 생각할 수 있다. 공은 질량이 같은 입자로 생각할 수 있다.

처음에 공 $i$는 위치 $X_i$에 있다. 초기 속도는 $V_i$이고 방향 $D_i = \pm 1$로 움직인다.

또한 상수 $C$가 주어진다. 임의의 순간에 공 $i$의 가속도 $A_i$와 속도 $V_i$는 방향이 같고, $A_i \cdot V_i = C$를 만족한다.

공이 여러 개이므로 움직이는 동안 서로 충돌할 수 있다. 모든 충돌은 완전 탄성 충돌이라고 가정한다.

여러 개의 질의가 주어진다. 각 질의는 두 정수 $t$와 $k$로 이루어진다. 시작한 지 정확히 $t$초 후 모든 공의 속도 중 $k$번째로 작은 값을 구해야 한다.

완전 탄성 충돌은 충돌에서 운동 에너지의 손실이 없는 충돌이다.

첫째 줄에 두 정수 $n$과 $C$가 주어진다. ($1 \le n \le 10^5$, $1 \le C \le 10^9$)

다음 $n$개의 줄이 주어진다. 그중 $i$번째 줄에는 세 정수 $V_i$, $X_i$, $D_i$가 주어진다. $V_i$는 공 $i$의 초기 속도 ($1 \le V_i \le 10^5$), $X_i$는 공 $i$의 초기 위치 ($1 \le X_i \le 10^9$), $D_i$는 공 $i$가 움직이는 방향이다.

다음 줄에는 정수 $1 \le q \le 10^5$가 주어지며, 이는 질의의 수이다. 그 뒤에 $q$개의 줄이 주어진다. 각 줄에는 두 정수 $1 \le t \le 10^9$와 $1 \le k \le n$이 주어진다.

각 질의마다 절대 오차가 $10^{-3}$ 이하인 답을 한 줄에 하나씩 출력한다.