Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $t$ ($1 \le t \le 1\,000$)~--- количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $n$ и $r$ ($3 \le n \le 2\,000$, $1 \le r \le 10^9$)~--- количество точек и максимальное расстояние для сдвига точки.

Следующие $n$ строк описывают точки. $i$-я из них содержит три целых числа $x_i$, $y_i$ и $c_i$ ($-10^9 \le x_i, y_i \le 10^9$, $1 \le c_i \le 2$)~--- координаты и цвет точки $i$ (1 ~--- белый, 2 ~--- черный).

Гарантируется, что сумма $n$ по всем наборам входных данных в каждом тесте не превосходит $2\,000$.