#include<bits/stdc++.h>
using namespace std;
typedef struct node
{
char ch;
node * next;
} node;
char firstNotRepeatingCharacter( string & s)
{
char ans = '_' ;
map< char ,node* > mp;
node * head = NULL ;
node * last;
node * temp1 = NULL ;
node * temp2 = new node[ 1 ] ;
temp2- > ch = '$' ;
temp2- > next = NULL ;
for ( int i = 0 ; i < s.size ( ) ; ++ i)
{
//cout << s[i] << endl;
//first occurence//
if ( mp.find ( s[ i] ) == mp.end ( ) )
{
node * temp = new node[ 1 ] ;
temp- > ch = s[ i] ;
temp- > next = NULL ;
if ( head == NULL )
{
head = temp;
last = temp;
mp.insert ( make_pair( s[ i] ,temp1) ) ;
}
else
{
last- > next = temp;
mp.insert ( make_pair( s[ i] ,last) ) ;
last = temp;
}
}
//Repeated occurence//
else
{
node * temp = mp[ s[ i] ] ;
if ( mp[ s[ i] ] ! = temp2)
{
if ( temp == temp1)
{
head = head- > next;
if ( ( head) ! = NULL ) { mp[ head- > ch] = temp1; }
else last = head;
mp[ s[ i] ] = temp2;
}
else if ( ( temp- > next) ! = NULL )
{
temp- > next = temp- > next- > next;
if ( ( temp- > next) ! = NULL ) { mp[ temp- > next- > ch] = temp; }
else last = temp;
mp[ s[ i] ] = temp2;
}
else
{
;
}
}
}
/*node *temp2 = head;
while(temp2 != NULL){cout << temp2->ch << "--";temp2 = temp2->next;}
cout << endl;*/
}
if ( head == NULL ) { ; }
else { ans = head- > ch; }
return ans;
}
int main( )
{
int T;
cin >> T;
while ( T-- )
{
string str;
cin >> str;
cout << str << " -> " << firstNotRepeatingCharacter( str) << endl;
}
return 0 ;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnR5cGVkZWYgc3RydWN0IG5vZGUKewogICAgY2hhciBjaDsKICAgIG5vZGUgKm5leHQ7Cn1ub2RlOwoKCgoKY2hhciBmaXJzdE5vdFJlcGVhdGluZ0NoYXJhY3RlcihzdHJpbmcgJnMpCnsKICBjaGFyIGFucyA9ICdfJzsKICBtYXA8Y2hhcixub2RlKj4gbXA7CiAgbm9kZSAqaGVhZCA9IE5VTEw7CiAgbm9kZSAqbGFzdDsKICBub2RlICp0ZW1wMSA9IE5VTEw7CiAgbm9kZSAqdGVtcDIgPSBuZXcgbm9kZVsxXTsKICB0ZW1wMi0+Y2ggPSAnJCc7CiAgdGVtcDItPm5leHQgPSBOVUxMOwogIGZvcihpbnQgaSA9IDA7aSA8IHMuc2l6ZSgpOysraSkKICB7CiAgICAvL2NvdXQgPDwgc1tpXSA8PCBlbmRsOwogICAgLy9maXJzdCBvY2N1cmVuY2UvLwogICAgaWYobXAuZmluZChzW2ldKSA9PSBtcC5lbmQoKSkKICAgIHsKICAgICAgbm9kZSAqdGVtcCA9IG5ldyBub2RlWzFdOwogICAgICB0ZW1wLT5jaCA9IHNbaV07CiAgICAgIHRlbXAtPm5leHQgPSBOVUxMOwogICAgICBpZihoZWFkID09IE5VTEwpCiAgICAgIHsKICAgICAgICBoZWFkID0gdGVtcDsKICAgICAgICBsYXN0ID0gdGVtcDsKICAgICAgICBtcC5pbnNlcnQobWFrZV9wYWlyKHNbaV0sdGVtcDEpKTsKICAgICAgfQogICAgICBlbHNlCiAgICAgIHsKICAgICAgICBsYXN0LT5uZXh0ID0gdGVtcDsKICAgICAgICBtcC5pbnNlcnQobWFrZV9wYWlyKHNbaV0sbGFzdCkpOwogICAgICAgIGxhc3QgPSB0ZW1wOyAKICAgICAgfQogICAgfQogICAgLy9SZXBlYXRlZCBvY2N1cmVuY2UvLwogICAgZWxzZQogICAgewogICAgICBub2RlICp0ZW1wID0gbXBbc1tpXV07CiAgICAgIGlmKG1wW3NbaV1dICE9IHRlbXAyKQogICAgICB7CiAgICAgICAgaWYodGVtcCA9PSB0ZW1wMSkKICAgICAgICB7CiAgICAgICAgICBoZWFkID0gaGVhZC0+bmV4dDsKICAgICAgICAgIGlmKChoZWFkKSE9TlVMTCl7bXBbaGVhZC0+Y2hdID0gdGVtcDE7fQogICAgICAgICAgZWxzZSBsYXN0ID0gaGVhZDsKICAgICAgICAgIG1wW3NbaV1dID0gdGVtcDI7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYoKHRlbXAtPm5leHQpICE9IE5VTEwpCiAgICAgICAgewogICAgICAgICAgdGVtcC0+bmV4dCA9IHRlbXAtPm5leHQtPm5leHQ7CiAgICAgICAgICBpZigodGVtcC0+bmV4dCkgIT0gTlVMTCl7bXBbdGVtcC0+bmV4dC0+Y2hdID0gdGVtcDt9CiAgICAgICAgICBlbHNlIGxhc3QgPSB0ZW1wOwogICAgICAgICAgbXBbc1tpXV0gPSB0ZW1wMjsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgIDsKICAgICAgICB9CiAgICAgfQogICAgfQogICAgLypub2RlICp0ZW1wMiA9IGhlYWQ7CiAgICB3aGlsZSh0ZW1wMiAhPSBOVUxMKXtjb3V0IDw8IHRlbXAyLT5jaCA8PCAiLS0iO3RlbXAyID0gdGVtcDItPm5leHQ7fQogICAgY291dCA8PCBlbmRsOyovCiAgfQogIGlmKGhlYWQgPT0gTlVMTCl7O30KICBlbHNlIHthbnMgPSBoZWFkLT5jaDt9CiAgcmV0dXJuIGFuczsKfQoKaW50IG1haW4oKQp7CiAgaW50IFQ7CiAgY2luID4+IFQ7CiAgd2hpbGUoVC0tKQogIHsKICBzdHJpbmcgc3RyOwogIGNpbiA+PiBzdHI7CiAgY291dCA8PCBzdHIgPDwgIiAtPiAgIiA8PCBmaXJzdE5vdFJlcGVhdGluZ0NoYXJhY3RlcihzdHIpPDwgZW5kbDsKICB9CiAgcmV0dXJuIDA7Cn0=
stdin
MTAKYWJhY2FiYWQKYWJhY2FiYWFiYWNhYmEKegpiY2IKYmNjY2NjY2NiCmFiY2RlZmdoaWprbG1ub3BxcnN0dXZ3eHl6aWZsc2tlY3puc2xramZhYmUKenp6CmJjY2NjY2NjY2NjY2NjeWIKeGRueHhsdnVwenV3Z2lnZXFqZ2dvc2dsanVobGl5YmtqcGlieWF0b2ZjamJmeHd0YWxjCm5ncmhocWJobnNpcGtjb3FqeXZpaWt2eGJ4eXBoc25qcGR4a2h0YWRsdHN1eGJmYnJrb2Y=
10
abacabad
abacabaabacaba
z
bcb
bcccccccb
abcdefghijklmnopqrstuvwxyziflskecznslkjfabe
zzz
bcccccccccccccyb
xdnxxlvupzuwgigeqjggosgljuhliybkjpibyatofcjbfxwtalc
ngrhhqbhnsipkcoqjyviikvxbxyphsnjpdxkhtadltsuxbfbrkof