Coin Change - Permutations - 2

medium

1. You are given a number n, representing the count of coins.
2. You are given n numbers, representing the denominations of n coins.
3. You are given a number "amt".
4. You are required to calculate and print the permutations of the n coins (same coin can be used again any number of times) using which the amount "amt" can be paid.

Note -&gt; Use the code snippet and follow the algorithm discussed in question video. The judge can't force you but the intention is to teach a concept. Play in spirit of the question.

Input Format

A number n n1 n2 .. n number of elements A number amt

Output Format

Check the sample output and question video

Constraints

1 &lt;= n &lt;= 30
0 &lt;= n1, n2, .. n elements &lt;= 20
0 &lt;= amt &lt;= 50

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

Output

2-2-3-.
2-3-2-.
2-5-.
3-2-2-.
5-2-.

Coin Change - Permutations - 1

Queens Combinations - 2d As 2d - Box Chooses