정수 $n, m > 0$과 정수 $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$이 주어집니다. 다음 조건을 만족하는 $n$개의 정점 $V = \{v_1, v_2, \dots, v_n\}$을 가진 트리 $T$를 구성하세요: $a_i \ne -1$인 각 정점 $v_i$에 대하여, 차수 $\deg_T(v_i)$를 $m$으로 나눈 나머지가 $a_i$와 같아야 합니다. 만약 $a_i = -1$이면, 정점 $v_i$의 차수에는 아무런 제한이 없습니다.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t$가 주어집니다 ($1 \le t \le 5 \cdot 10^5$). 각 테스트 케이스에 대하여:

첫 번째 줄에는 트리의 정점 개수와 모듈러 값을 나타내는 두 정수 $n$과 $m$이 주어집니다 ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$).

다음 줄에는 요구되는 나머지를 나타내는 $n$개의 정수 $a_1, a_2, \dots, a_n$이 주어집니다 ($-1 \le a_i < m$).

모든 테스트 케이스에서 $n$의 합은 $5 \cdot 10^5$을 초과하지 않습니다.

출력

각 테스트 케이스마다, 그러한 $n$개의 정점을 가진 트리가 존재하면 "YES"(대소문자 무관)를 출력하고, 이어서 $n - 1$개의 줄에 각 간선의 양 끝점을 나타내는 두 정수를 출력합니다. 그렇지 않으면 "NO"(대소문자 무관)를 출력합니다.

예제

입력

6
1 5
0
2 3
1 1
5 4
0 1 1 1 1
6 2
1 0 0 0 0 1
3 2
1 1 1
4 10
3 3 1 1

출력

YES
YES
1 2
YES
1 2
1 3
1 4
1 5
YES
1 2
2 3
3 4
4 5
5 6
NO
NO

노트

첫 번째 테스트 케이스에서는 $n = 1$개의 정점, $m = 5$, 그리고 차수 나머지 배열 $b = [0]$인 트리를 만들어야 합니다. 정점이 하나뿐이면 간선이 있을 수 없으므로 가능한 트리는 차수가 $0$인 단일 정점 하나뿐입니다. $0 \bmod 5 = 0$이므로 조건을 만족하며, 따라서 답은 "YES"입니다.

두 번째 테스트 케이스에서는 $n = 2$개의 정점과 $m = 3$, 나머지 $b = [1, 1]$인 트리가 필요하며, 이는 두 차수 모두 모듈러 $3$에 대해 $1$과 합동이어야 함을 의미합니다. 두 정점 위의 트리는 단일 간선 $1-2$ 하나뿐입니다. 그 차수는 $(1, 1)$이고 실제로 $1 \bmod 3 = 1$이므로 답은 "YES"이며 "1 2"를 출력하면 유효합니다.

세 번째 테스트 케이스에서는 $n = 5$, $m = 4$, 나머지 $b = [0, 1, 1, 1, 1]$이 필요합니다: 첫 번째 정점의 차수는 $4$로 나누어떨어져야 하고, 나머지 네 정점은 $\text{degree} \equiv 1 \pmod 4$를 만족해야 합니다. 자연스러운 구성은 정점 $1$을 중심으로 하는 성형(star) 그래프입니다: $1$을 다른 모든 정점에 연결합니다. 그러면 $\deg(1) = 4$이고 $4 \bmod 4 = 0$이며, $2, 3, 4, 5$는 각각 차수가 $1$이고 $1 \bmod 4 = 1$입니다. 따라서 답은 "YES"이고, 간선 "1 2", "1 3", "1 4", "1 5"가 조건을 만족합니다.

네 번째 테스트 케이스에서는 $n = 6$, $m = 2$, 나머지 $b = [1, 0, 0, 0, 0, 1]$인 트리가 필요합니다. 즉, 양 끝점은 홀수 차수를 가져야 하고 가운데 네 정점은 짝수 차수를 가져야 합니다. 모듈러 $2$에서 이는 순전히 홀짝성 제약입니다. 단순 경로 $1-2-3-4-5-6$이 완벽하게 들어맞습니다: 정점 $1$과 $6$은 차수가 $1$(홀수)이고, 정점 $2, 3, 4, 5$는 차수가 $2$(짝수)입니다. 따라서 답은 "YES"이며 경로의 간선들이 올바른 답이 됩니다.

다섯 번째 테스트 케이스에서는 $n = 3$, $m = 2$, $b = [1, 1, 1]$인 그래프(특히 트리)를 만들어야 하므로 모든 정점이 홀수 차수를 가져야 합니다. 이는 불가능합니다: 모든 무방향 그래프에서 홀수 차수 정점의 개수는 항상 짝수이므로, 어떤 간선 집합에 대해서도 세 개의 홀수 차수가 나타날 수 없습니다. 따라서 판정은 "NO"입니다.

여섯 번째 테스트 케이스에서는 $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$입니다. $m > n - 1 = 3$이므로 모듈러 $10$에 대한 나머지는 차수 자체와 같아서 정확히 $\deg = [3, 3, 1, 1]$이 요구됩니다. 이는 두 정점이 다른 모든 정점과 인접하도록 강제하며($4$개 정점 그래프에서 차수 $3$), $n > 2$일 때 그러한 두 정점 쌍은 임의의 세 번째 정점과 함께 필연적으로 사이클을 형성합니다. 트리는 사이클을 포함할 수 없으므로 판정은 마찬가지로 "NO"입니다.