У Беси и Эльзы по n пирогов. Каждый из 2n пирогов имеет величину вкусности по мнению Беси и величину вкусности (возможно отличающуюся) по мнению Эльзы.

Беси хочет отдать один из своих пирогов Эльзе. Если Эльза получит пирог от Беси, она должна будет отдать один из своих пирогов Беси. Чтобы не оказаться ни скупой, ни щедрой, Эльза постарается выбрать пирог, как минимум, такой же вкусный (по мнению Эльзы) как она получила, но не более чем на d единиц вкуснее. Такой пирог может не существовать, в этом случае Эльза сбежит в Японию.

Но если Эльза отдаст Беси пирог взамен, то Беси аналогично постарается отдать Эльзе пирог, как минимум такой же вкусный (по мнению Беси), но не более чем на d единиц вкуснее, чем кусок, который она получила. Если Беси не сможет, то тоже сбежит. Иначе отдаст кусок Эльзе. Этот цикл продолжается, пока возможно, или пока одна из коров не получит кусок с величиной вкусности равной 0, в этом случае процесс заканчивается и обе коровы счастливы.

Заметим, что один и тот же кусок не может быть подарен дважды, и кусок не может вернуться той корове, которая его дарила.

Для каждого из n кусков Беси может выбрать его как начальный подарок Эльзе. Определите минимальное количество кусков, которые могут быть подарены так, чтобы обе коровы оказались счастливы.

Входные данные

Первая строка содержит два целых числа n (1 ≤ n ≤ 105) и d (0 ≤ d ≤ 109). Следующие 2n строк содержат по два целых числа, разделённых пробелом, соответственно обозначающие вкусность данного куска по мнению Беси и по мнению Эльзы.

Первые n строк о кусках Беси, а оставшиеся n строк о кусках Эльзы.

Гарантируется, что все величины вкусности в интервале [0, 109].

Выходные данные

На выводе должно быть n строк. Строка i должна содержать одно целое число: минимальное количество кусков, которое может быть подарено при счастливом исходе, если Беси начнёт с куска i. Если счастливый исход при начале с куска i невозможен, то строка i должна содержать -1.