#include <cstdio>
struct kolejka
{
int priorytet;
kolejka *next;
};
void dodaj(kolejka *&start, char znak);
void wypisz(kolejka *&start);
void usunwszo(kolejka *&start);
void starter()
{
kolejka *start = NULL;
int element;
element = getchar();
while(element>='A' && element <= 'z')
{
dodaj(start,element);
element = getchar();
}
wypisz(start);
usunwszo(start);
}
int main()
{
// kolejka *start = NULL;
int t;
char x;
scanf("%d",&t);
x=getchar(); //ABY USUNAC '0' Z TESTOW
while(t--) starter();
return 0;
}
void dodaj(kolejka *&start, char znak)
{
int prior = int(znak);
if(!start)
{
start = new kolejka;
start->priorytet = prior;
start->next = NULL;
}
else if(start->priorytet < prior)
{
usunwszo(start);
start = new kolejka;
start->priorytet = prior;
start->next = NULL;
}
else
{
kolejka *p=start, *temp;
while((p->next) && (prior < p->next->priorytet))
{
p=p->next;
}
temp = new kolejka;
temp->priorytet = prior;
temp->next = p->next;
p->next = temp;
usunwszo(temp->next);
}
}
void wypisz(kolejka *&start)
{
kolejka *p = start;
if(p)
{
while(p)
{
printf("%c",p->priorytet);
p=p->next;
}
printf("\n");
}
// else cout<<"Kolejka jest pusta :/\n";
}
void usunwszo(kolejka *&start)
{
kolejka *p;
while(start)
{
p = start;
start=start->next;
delete p;
}
}
I2luY2x1ZGUgPGNzdGRpbz4KCnN0cnVjdCBrb2xlamthCnsKICAgIGludCBwcmlvcnl0ZXQ7CiAgICBrb2xlamthICpuZXh0Owp9Owp2b2lkIGRvZGFqKGtvbGVqa2EgKiZzdGFydCwgY2hhciB6bmFrKTsKdm9pZCB3eXBpc3ooa29sZWprYSAqJnN0YXJ0KTsKdm9pZCB1c3Vud3N6byhrb2xlamthIComc3RhcnQpOwoKdm9pZCBzdGFydGVyKCkKewogICAga29sZWprYSAqc3RhcnQgPSBOVUxMOwogICAgaW50IGVsZW1lbnQ7CiAgICBlbGVtZW50ID0gZ2V0Y2hhcigpOwogICAgd2hpbGUoZWxlbWVudD49J0EnICYmIGVsZW1lbnQgPD0gJ3onKQogICAgewogICAgICAgIGRvZGFqKHN0YXJ0LGVsZW1lbnQpOwogICAgICAgIGVsZW1lbnQgPSBnZXRjaGFyKCk7CiAgICB9CiAgICB3eXBpc3ooc3RhcnQpOwogICAgdXN1bndzem8oc3RhcnQpOwp9CmludCBtYWluKCkKewogICAgLy8ga29sZWprYSAqc3RhcnQgPSBOVUxMOwogICAgaW50IHQ7CiAgICBjaGFyIHg7CiAgICBzY2FuZigiJWQiLCZ0KTsKICAgIHg9Z2V0Y2hhcigpOyAvL0FCWSBVU1VOQUMgJzAnIFogVEVTVE9XCiAgICB3aGlsZSh0LS0pIHN0YXJ0ZXIoKTsKICAgIHJldHVybiAwOwp9Cgp2b2lkIGRvZGFqKGtvbGVqa2EgKiZzdGFydCwgY2hhciB6bmFrKQp7CiAgICBpbnQgcHJpb3IgPSBpbnQoem5hayk7CiAgICBpZighc3RhcnQpCiAgICB7CiAgICAgICAgc3RhcnQgPSBuZXcga29sZWprYTsKICAgICAgICBzdGFydC0+cHJpb3J5dGV0ID0gcHJpb3I7CiAgICAgICAgc3RhcnQtPm5leHQgPSBOVUxMOwogICAgfQogICAgZWxzZSBpZihzdGFydC0+cHJpb3J5dGV0IDwgcHJpb3IpCiAgICB7CiAgICAgICAgdXN1bndzem8oc3RhcnQpOwogICAgICAgIHN0YXJ0ID0gbmV3IGtvbGVqa2E7CiAgICAgICAgc3RhcnQtPnByaW9yeXRldCA9IHByaW9yOwogICAgICAgIHN0YXJ0LT5uZXh0ID0gTlVMTDsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBrb2xlamthICpwPXN0YXJ0LCAqdGVtcDsKICAgICAgICB3aGlsZSgocC0+bmV4dCkgJiYgKHByaW9yIDwgcC0+bmV4dC0+cHJpb3J5dGV0KSkKICAgICAgICB7CiAgICAgICAgICAgIHA9cC0+bmV4dDsKICAgICAgICB9CiAgICAgICAgdGVtcCA9IG5ldyBrb2xlamthOwogICAgICAgIHRlbXAtPnByaW9yeXRldCA9IHByaW9yOwogICAgICAgIHRlbXAtPm5leHQgPSBwLT5uZXh0OwogICAgICAgIHAtPm5leHQgPSB0ZW1wOwogICAgICAgIHVzdW53c3pvKHRlbXAtPm5leHQpOwogICAgfQp9CnZvaWQgd3lwaXN6KGtvbGVqa2EgKiZzdGFydCkKewogICAga29sZWprYSAqcCA9IHN0YXJ0OwogICAgaWYocCkKICAgIHsKICAgICAgICB3aGlsZShwKQogICAgICAgIHsKICAgICAgICAgICAgcHJpbnRmKCIlYyIscC0+cHJpb3J5dGV0KTsKICAgICAgICAgICAgcD1wLT5uZXh0OwogICAgICAgIH0KICAgICAgICBwcmludGYoIlxuIik7CiAgICB9CiAgICAvLyBlbHNlIGNvdXQ8PCJLb2xlamthIGplc3QgcHVzdGEgOi9cbiI7Cn0KCnZvaWQgdXN1bndzem8oa29sZWprYSAqJnN0YXJ0KQp7CiAgICBrb2xlamthICpwOwogICAgd2hpbGUoc3RhcnQpCiAgICB7CiAgICAgICAgcCA9IHN0YXJ0OwogICAgICAgIHN0YXJ0PXN0YXJ0LT5uZXh0OwogICAgICAgIGRlbGV0ZSBwOwogICAgfQp9Cg==