Description

Permutation EX (Hard Version)

Given N digits, we can write them down one by one (in some order) to form a number, say X.

For example, given 1 0 2 3 1, we can form a number 11032.

What are the all possible X such that X can be divided by a positive integer M?

Note that X cannot start with 0. That is, 00123 is not a valid number.

Input

First line contains a number T, indicating that there are T questions follow.

Each question consists of 2 lines. In the first line, there are two positive number N and M, described in Problem Description. In the second line, there are N digits (0~9), each of them seperated by a space.

---

It is guaranteed that

• T <= 10
• Testcase 1
  • N < 10, M = 1, digits does not contain 0 and there is no duplicate digit in X.
• Testcase 2
  • N < 10, M = 1, digits does not contain 0
• Testcase 3 & 4
  • N < 10, M < 10
• Testcase 5
  • N < 100, M < 10⁶, total number of possible permutation of those N digits won't exceed 10⁸
  • Hint: think about how to store the numbers

Output

For each question, print out all number formed by those N digits such that it can be divided by M, in ascending order.

Print out an empty line at the end of each question.

For more information, please refer to Sample Input & Sample Output.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss