10705 - The Fun Number System

Problem A
The Fun Number System
Input: standard input
Output: standard output
Time Limit: 1 second

一個 k bit 的二補數，使用 bits 的編號從 0 到 k - 1，最大震級的 bit (即位置在 k - 1) 值為  –2^k–1 ，而其他位置 i (0 <= i < k - 1)的值為 2ⁱ。例如：一個 3 bits 的數字 101 被計算為 -2²+0+2⁰ = -3 ，而 011 as –0+2¹+2⁰ = 3。而負數權重的 bit 被稱作 negabit ，反之正權重的 bit 被稱作 posibit。

有趣的數字系統 是一個位置二元數字系統，根據每一個 bit 是 negabit 還是 posibit 決定。例如：一個 3-bit 的 有趣的數字系統 Fun3，位置 0, 2 的 bit 是 posibit，而位置 1 的 bit 是 negabit。因此 (111)_Fun3 被計算為 2² –2¹ + 1 = 3。

現在給你一個指定的 k-bit 的 有趣的數字系統，然後給定一個整數 N (可以是負數)，必須輸出一個 k-bits 的藉由 Funk 表示 N，或者回報無法表示整數 N。

例如：–1 在 Fun3 (給定如上述描述)中,  011 (相當於 0–2¹+2⁰ ), 但要表示 6 在 Fun3 是不可能的。

輸入格式Input

第一行會有一個整數 t (0 <t =100) 表示有幾個測資組。

每組測資會有連續三行，第一行會有一個正整數 k(1<=k <=64)，第二行會有一個長度為 k 的字串，這個字串只由字符 n 跟 p 構成，描述數字系統的資料，每個 n (p) 表示該位置是
negabit (posibit)，第三行會有一個整數 N (-2⁶³ =N<2⁶³)，表示要用 Funk 表示這個數字。

輸出格式Output

對於每組測資，輸出一行 k-bit 的字串，表示 N 在 Funk 的表示法，如果沒有辦法表示輸出 "Impossible" 不含雙引號。

Sample Input                              Output for Sample Input

2 3 pnp 6 4 ppnn 10

Impossible 1110

---

Problem source: Iranian Contest

Special Thanks Monirul Hasan, EPS.