Healthy dinner party

Problem code: C4

All submissions for this problem are available.

The Chef is having a dinner party and invited over all his friends. His guests
being fairly health conscious have exact protein requirements, and The Chef wishes to oblige them all.

The Chef will cook dishes for each individual guest using the ingredients in his kitchen. Each ingredient has a specific amount of protein. The complete dish will have a protein content value equal to the sum of the protein
contents of the individual ingredients. To cook a dish, The Chef can use any of the ingredients which appear on his shelf, but only in the order which they appear on the shelf. The same ingredient may appear multiple times, and can also be used as many times as it appears.

There are multiple ways to choose ingredients following the rules given above. However, The Chef is only interested in choosing the set of ingredients that appear first in a lexicographically ordered list of ingredients which satisfy the protein constraints. Your job is to write a program that helps The Chef figure out which dish to serve!

Input

The first line of input contains t, the number of guests invited by The Chef (about 200).

Each test consists of three lines:

  • The first line consists of one integer 1 <= k <= 26 (the number of unique ingredients on the shelf) and than k
    space-separated positive integers from the set {1, 2, ... ,15} describing the protein content for each ingredient in an alphabetically sorted list of unique ingredients. (the first protein value corresponds with ingredient a, the second corresponds with the protein value for ingredient b, and so on).
  • The second line contains L - a sequence of lower-case letters of the Latin alphabet (at most 1000) which signify the name of the ingredient.
  • The third line contains one positive integer S which specifies the exact protein requirement of this guest (1 < S < 500).

Output

For each testcase either output the sequence of ingredients as described above, or the word 'IMPOSSIBLE' if no such subsequence exists.

Example

Input:
3
5 12 1 12 4 4
acccdadceb
2
3 5 4 6
abcbacbabcc
15
2 3 4
baba
7

Output:
IMPOSSIBLE
aaa
ab



Comments:

For the first guest we have five ingredients: a, b, c, d, e with protein values 12 1 12 4 4 respectively. To achieve a total protein value equal to 2 we need two ingredients b. But there is only one, thus the answer is IMPOSSIBLE.

For the second guest we can achieve a total protein value of 15 with the ingredients taken as: abc, bca, acb, cab, cba, bac, or aaa. Of these, the first according to lexicographic order is aaa.

For the third guest, out of the two possibilities, ab is the correct answer.

Author: admin
Date Added: 20-04-2009
Time Limit: 5 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions