평가 방해

드디어 경제학 과제 에세이를 평가에 제출할 때가 되었다! 각 에세이는 단어 수 $w$와 품질 $q$로 특징지어진다. 요구되는 단어 수는 $W$이므로, 에세이의 $w$가 $W$에 가까울수록 더 좋은 점수를 기대할 수 있다. 물론 품질이 높을수록 좋다. 그러나 한 에세이가 다른 에세이보다 품질은 더 좋고 $W$에서 더 크게 벗어날 수도 있으므로, 어느 쪽이 더 나은지는 분명하지 않다.

경제학을 공부한 학생이라면 이런 상황이 파레토 지배로 설명된다는 것을 알고 있을 것이다. 형식적으로, 에세이 $A$가 에세이 $B$를 파레토 의미에서 지배한다는 것은 $|w_A - W| \le |w_B - W|$이고 $q_A \ge q_B$이며, 이 두 부등식 중 적어도 하나가 엄격한 부등식일 때이다.

교수는 이 관계로 에세이를 채점한다. 먼저 다른 어떤 에세이에게도 지배되지 않는 가장 좋은 에세이들을 모두 찾는다. 이 에세이들은 같은 점수를 받으며, 그 점수는 올해 학생들 중 가장 높다(그래도 기대에 못 미칠 수 있다!). 그다음 점수를 받은 에세이를 제거하고 절차를 반복하는데, 이번에는 점수가 더 낮아진다. 정확한 알고리즘은 다음과 같다.

• 모든 에세이는 1부터 $N$까지 번호가 매겨진다.
• 각 에세이는 작업 중, 보류, 표시됨 중 하나의 상태를 가진다. 처음에는 모든 에세이가 작업 중이다.
• 변수 $r$은 에세이의 순위를 나타내며, 값이 작을수록 좋다. 처음에 $r \gets 1$이다.
• 작업 중인 에세이가 있는 동안 다음을 반복한다.
  • 번호 1부터 $N$까지 순회한다. $i$번째 에세이가 작업 중이면
    • 번호 $i+1$부터 $N$까지 순회한다. $j$번째 에세이가 작업 중이면 에세이 $i$와 $j$를 지배 관계로 비교한다.
      • $i$가 $j$를 지배하면 $j$를 보류로 바꾼다.
      • $j$가 $i$를 지배하면 $i$를 보류로 바꾸고 반복을 멈춘다.
    • $i$번째 에세이가 여전히 작업 중이면 순위 $r$을 받고 표시됨으로 바뀐다.
  • 모든 보류 에세이를 다시 작업 중으로 바꾼다.
  • $r$을 1 늘린다.

교수의 전체 평가가 너무 오래 걸리면 학부가 평가를 넘겨받고 최종 점수는 간단한 객관식 퀴즈로 정해진다는 이야기를 누군가에게 들었다. 엄밀하게 계산해 보니, 이런 일이 일어나려면 에세이 비교 횟수가 적어도 $N^3 / 20$이어야 한다. 이 평가 절차를 방해하는 방법을 찾아라.

입력은 한 줄이며, 공백으로 구분된 두 수 $N$ $(2 \le N \le 10^3)$과 $W$ $(0 \le W \le 10^4)$가 주어진다.

$N$줄을 출력한다. $i$번째 줄 ($1 \le i \le N$)에는 $i$번째 에세이의 단어 수 $w_i$와 품질 $q_i$를 출력한다. 두 값은 $0 \le w_i \le 10^4$, $0 \le q_i \le 10^3$을 만족하는 정수여야 한다. 같은 쌍의 숫자로 표현되는 에세이가 둘 이상 있어서는 안 된다. 이는 담합으로 간주되므로 반드시 피해야 한다.