Under construction

Still being built. Things may change

The divisor conquers

Time limit8sMemory limit512 MB

Summary
Place the N cards one at a time so each new card divides the sum of the cards already down, and print the lexicographically smallest winning order or No.
Level

Medium7 of 10

Topics
Backtracking, Greedy, Math, Dynamic programming
Solved
No attempts yet

Problem

"Divisor is the Conquerer" is a solitaire card game. The rules follow.

First, draw NN cards from a deck. The game uses only the drawn cards, and the rest of the deck stays out of play.

Then put the cards down on the table one at a time. The first card can be any of them. After that you may put down only a card that conquers the cards already on the table. A card conquers a set of cards when the number on the card divides the sum of the numbers in the set. For example, card 77 conquers the set {5,11,12}\{5, 11, 12\}, but card 1111 does not conquer the set {5,7,12}\{5, 7, 12\}.

You win once all NN drawn cards are on the table. You lose if at some point no card can be put down.

Input

The input holds several test cases.

Each test case is two lines. The first line has the number of cards NN (1≤N≤521 \le N \le 52). The second line has the numbers on the cards, c1,…,cNc_1, \dots, c_N (1≤ci≤131 \le c_i \le 13), separated by spaces. Within one test case at most four cards carry the same number.

A 00 in place of NN ends the input.

Output

Print one line for each test case.

If a winning order exists, print the order the cards are put down as NN integers separated by single spaces. When several winning orders exist, print only the lexicographically smallest one. For two sequences AA and BB of the same length, AA is lexicographically smaller than BB if Ai<BiA_i < B_i at the smallest index ii with Ai≠BiA_i \ne B_i.

If no winning order exists, print No.

Examples2

  1. Example 1

    Input
    5
    1 2 3 3 7
    4
    2 3 3 3
    0
    
    Expected output
    3 3 1 7 2
    No
    
  2. Example 2

    Input
    1
    1
    1
    13
    2
    2 3
    3
    5 7 11
    0
    
    Expected output
    1
    13
    No
    No