If you find yourself in Nevada at an abandoned nuclear range during Halloween time, you’ll become a witness of an unusual show. Here Ghostbusters hold annual tests for new versions of their proton packs. There are n Ghostbusters and n portable traps with ghosts, all are located on a semicircle. Each trap contains exactly one ghost. The ghosts may be of different types, but each Ghostbuster can neutralize with his weapon only one type of the evil spirits.
On the count of three all ghost traps open at once and all Ghostbusters start to fire. Of course, each Ghostbuster shoots at the ghost, which his proton gun is able to neutralize. The most important thing here is not to cross proton beams of the guns.
You know positions of all Ghostbusters and all the traps in this year’s tests. For each Ghostbuster determine which ghost he should shoot at, so that all the ghosts are neutralized and no two gun beams cross. You can assume that all proton beams are in the same horizontal plane and they don’t shoot ghosts through in case of a hit.
Input
In the first line there is an integer n that is the number of Ghostbusters (1 ≤ n ≤ 5 000). In the second line the sequence of 2 n Latin letters is written, describing the allocation of the Ghostbusters and the traps on the semicircle. Uppercase letters correspond to the Ghostbusters and lowercase letters correspond to the traps. For example, “a” stands for a trap with the ghost of type “a”, while “A” stands for the Ghostbuster with the gun neutralizing ghosts of type “a”. The sequence has exactly n lowercase letters and exactly n uppercase letters.
Output
If the problem has a solution, output n space-separated integers g 1, g 2, …, g n, where g i is the number of the ghost i-th Ghostbuster should shoot at. Both Ghostbusters and ghosts are numbered with integers from 1 to n in the order of their positions along the semicircle. All g i must be pairwise different. If the problem has several solutions, output any of them. If the problem has no solution, output “Impossible”.
Example
| input | output |
|---|---|
2 |
2 1 |
2 |
Impossible |
1 |
Impossible |
Hint
/*
* @Author: lyuc
* @Date: 2017-04-30 17:08:16
* @Last Modified by: lyuc
* @Last Modified time: 2017-04-30 18:14:17
*/
/**
* 题意：有n个怪兽（小写字母），n个人（大写字母）在一个半圆的底面，如图，A只能杀死a，B只能杀死b
* 如果相互的弹道不能交叉，问是否存在全部杀死的情况，如果是输出每个人杀死怪兽的编号，否则
* 输出Impossible
* 思路：暴力模拟，一直取相邻的两个元素,如果取到没有相邻的了就输出不可能，否则就输出可能
*/
#include <iostream>
#include <stdio.h>
#include <map>
#include <string.h>
#include <vector>
using namespace std;
int n;
int pm[];
int mm[];
int po,ms;
char str[];
bool vis[];
int pos[];
void init(){
po=;
ms=;
memset(vis,false,sizeof vis);
memset(pos,,sizeof pos);
}
int main(){
// freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
scanf("%s",str);
init();
for(int i=;i<n*;i++){
if(str[i]>='A'&&str[i]<='Z'){
pm[i]=po++;
}else{
mm[i]=ms++;
}
}
int tmp=n*;
bool F=true;
while(tmp){
bool flag=false;
for(int i=;i<n*;i++){
if(vis[i]) continue;
for(int j=i+;j<n*;j++){
if(vis[j]) continue;
else{
if(str[i]>='A'&&str[i]<='Z'){
if(str[i]-'A'+'a'==str[j]){
pos[pm[i]]=mm[j];
vis[i]=true;
vis[j]=true;
flag=true;
tmp-=;
}
break;
}else{
if(str[i]-'a'+'A'==str[j]){
pos[pm[j]]=mm[i];
vis[i]=true;
vis[j]=true;
flag=true;
tmp-=;
}
break;
}
}
}
}
if(flag==false){
F=false;
break;
}
}
if(F==false){
puts("Impossible");
}else{
for(int i=;i<po;i++)
printf(i==?"%d":" %d",pos[i]);
printf("\n");
}
}
return ;
}