Tuesday, 22 November 2016

BYTESM2 - Philosophers Stone

Problem Statement
One of the secret chambers in Hogwarts is full of philosopher’s stones. The floor of the chamber is covered by h × w square tiles, where there are h rows of tiles from front (first row) to back (last row) and w columns of tiles from left to right. Each tile has 1 to 100 stones on it. Harry has to grab as many philosopher’s stones as possible, subject to the following restrictions:
  • He starts by choosing any tile in the first row, and collects the philosopher’s stones on that tile. Then, he moves to a tile in the next row, collects the philosopher’s stones on the tile, and so on until he reaches the last row.
  • When he moves from one tile to a tile in the next row, he can only move to the tile just below it or diagonally to the left or right.
Given the values of h and w, and the number of philosopher’s stones on each tile, write a program to compute the maximum possible number of philosopher’s stones Harry can grab in one single trip from the first row to the last row.

Input

The first line consists of a single integer T, the number of test cases. In each of the test cases, the first line has two integers. The first integer h (1 <= h <= 100) is the number of rows of tiles on the floor. The second integer w (1 <= w <= 100) is the number of columns of tiles on the floor. Next, there are h lines of inputs. The i-th line of these, specifies the number of philosopher’s stones in each tile of the i-th row from the front. Each line has w integers, where each integer m (0 <= m <= 100) is the number of philosopher’s stones on that tile. The integers are separated by a space character.

Output

The output should consist of T lines, (1 <= T <= 100), one for each test case. Each line consists of a single integer, which is the maximum possible number of philosopher’s stones Harry can grab, in one single trip from the first row to the last row for the corresponding test case.

Example

Input:
1
6 5
3 1 7 4 2
2 1 3 1 1
1 2 2 1 8
2 2 1 5 3
2 1 4 4 4
5 2 7 5 1

Output:
32  
//7+1+8+5+4+7=32
 
Problem Link : http://www.spoj.com/problems/BYTESM2/
 
The idea : The idea here is to use dynamic programming .  Use the bottom up 
approach. 
  • There is no need to use another matrix for dp as the given
matrix is enough and once we have moved from one row to another we do not need
the older values. 
  • Now we can use the formula arr[i][j]=max(arr[i-1][j-1],arr[i-1][j],
    arr[i+1][j+1])+arr[i][j].
     
     
    Problem Code:
    #include <iostream>
    #include<bits/stdc++.h>
    using namespace std;
    long long int dp[101][101];
    long long int max(long long int a,long long int b,long long int c)
    {
        long long int answer=INT_MIN;
        answer=max(answer,a);
        answer=max(answer,b);
        answer=max(answer,c);
        return answer;
    }
    
    
    int main() 
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            
            
            int h,w;
            scanf("%d %d",&h,&w);
            long long int **arr;
            arr=new long long int*[h];
            for(int i=0;i<h;i++)
            {
            arr[i]=new long long int[w];
            }
            
            for(int i=0;i<h;i++)
            {
                for(int j=0;j<w;j++)
                {
                    scanf("%lld",&arr[i][j]);
                }
            }
           
           for(int i=1;i<h;i++)
           {
               for(int j=0;j<w;j++)
               {
                   long long int answer=INT_MIN;
                   long long int fromtop=INT_MIN;
                   long long int fromdiagleft=INT_MIN;
                   long long int fromdiagright=INT_MIN;
                   
                   if(j==0)
                   {
                      answer=max(arr[i-1][j],arr[i-1][j+1]); 
                   }
                   else
                    if(j==w-1)
                   {
                       answer=max(arr[i-1][j],arr[i-1][j-1]);
                   }
                   else
                   {
                       answer=max(arr[i-1][j+1],arr[i-1][j],arr[i-1][j-1]);
                   }
                   arr[i][j]=answer+arr[i][j];
                   
               }
           }
           long long int answer=INT_MIN;
           for(int j=0;j<w;j++)
           {
               answer=max(answer,arr[h-1][j]);
           }
            
        
            cout<<answer<<endl;
        }
     
     return 0;
    }
     
 

Monday, 21 November 2016

Dividing Stamps

Are you fond of collecting some kind of stuff? Mike is crazy about collecting stamps. He is an active member of Stamp Collecting Сommunity(SCC).
SCC consists of N members which are fond of philately. A few days ago Mike argued with the others from SCC. Mike told them that all stamps of the members could be divided in such a way that i'th member would get i postage stamps. Now Mike wants to know if he was right. The next SCC meeting is tomorrow. Mike still has no answer.
So, help Mike! There are N members in the SCC, i'th member has Ci stamps in his collection. Your task is to determine if it is possible to redistribute C1 + C2 + ... + Cn stamps among the members of SCC thus that i'th member would get i stamps.

Input

The first line contains one integer N, denoting the number of members of SCC.
The second line contains N integers Ci, denoting the numbers of the stamps in the collection of i'th member.

Output

The first line should contain YES, if we can obtain the required division, otherwise NO.

Constraints

1 ≤ N ≤ 100 000;
1 ≤ Ci ≤ 109.

Examples

Input:
5
7 4 1 1 2

Output:
YES

Input:
5
1 1 1 1 1

Output:
NO
 
Problem Link : DIVIDING

The idea :

The idea is that the sum of all elements should be equal to sum of all numbers from 1 to N. 

The Code :

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main()
{
        int n,i;
        long int sum=0,c;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%ld",&c);
            sum+=c;
        }
        if(sum==(n*(n+1))/2)
            printf("YES\n");
        else
            printf("NO\n");
    return 0;
}


Maximum Weight Difference

Chef has gone shopping with his 5-year old son. They have bought N items so far. The items are numbered from 1 to N, and the item i weighs Wi grams.
Chef's son insists on helping his father in carrying the items. He wants his dad to give him a few items. Chef does not want to burden his son. But he won't stop bothering him unless he is given a few items to carry. So Chef decides to give him some items. Obviously, Chef wants to give the kid less weight to carry.
However, his son is a smart kid. To avoid being given the bare minimum weight to carry, he suggests that the items are split into two groups, and one group contains exactly K items. Then Chef will carry the heavier group, and his son will carry the other group.
Help the Chef in deciding which items should the son take. Your task will be simple. Tell the Chef the maximum possible difference between the weight carried by him and the weight carried by the kid.

Input:

The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow. The first line of each test contains two space-separated integers N and K. The next line contains N space-separated integers W1, W2, ..., WN.

Output:

For each test case, output the maximum possible difference between the weights carried by both in grams.

Constraints:

  • 1 ≤ T ≤ 100
  • 1 ≤ K < N ≤ 100
  • 1 ≤ Wi ≤ 100000 (105)

Example:

Input:
2
5 2
8 4 5 2 10
8 3
1 1 1 1 1 1 1 1

Output:
17
2

Explanation:

Case #1: The optimal way is that Chef gives his son K=2 items with weights 2 and 4. Chef carries the rest of the items himself. Thus the difference is: (8+5+10) − (4+2) = 23 − 6 = 17.
Case #2: Chef gives his son 3 items and he carries 5 items himself.

Problem LinkMAXDIFF

The idea :
First take out sum of all element let it be Sum.The idea is to take the largest k elements and smallest k elements.  Let this be largek and smallk . Now take out the rest part as  largeOther=Sum-largek and smallOther=Sum-smallk. Now print the  maximum of absolute difference of largek and largeOther and smallk and smallOther.

The Code:

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,k;
        scanf("%d %d",&n,&k);
        vector<int> elements;
        int sum=0;
        for(int i=0;i<n;i++)
        {
            int number;
            scanf("%d",&number);
            sum+=number;
            elements.push_back(number);
        }
        sort(elements.begin(),elements.end());
        int bigPart=0;
        int bigOtherPart=0;
        int smallPart=0;
        int smallOtherPart=0;
       
        for(int i=0;i<k;i++)
        smallPart+=elements[i];
        smallOtherPart=sum-smallPart;
       
        int last=n-1;
        while(k--)
        {
            bigPart+=elements[last];       
            last--;
        }
       
        bigOtherPart=sum-bigPart;
       
       
        int answer=max(abs(smallPart-smallOtherPart),abs(bigPart-bigOtherPart));
        cout<<answer<<endl;
       
       
       
       
    }

    return 0;
}




Now take out largeOther=

Sunday, 20 November 2016

Arranging Cup-cakes

Problem Statement
Our Chef is catering for a big corporate office party and is busy preparing different mouth watering dishes. The host has insisted that he serves his delicious cupcakes for dessert.
On the day of the party, the Chef was over-seeing all the food arrangements as well, ensuring that every item was in its designated position. The host was satisfied with everything except the cupcakes. He noticed they were arranged neatly in the shape of a rectangle. He asks the Chef to make it as square-like as possible.
The Chef is in no mood to waste his cupcakes by transforming it into a perfect square arrangement. Instead, to fool the host, he asks you to arrange the N cupcakes as a rectangle so that the difference between the length and the width is minimized.

Input

The first line of the input file contains an integer T, the number of test cases. Each of the following T lines contains a single integer N denoting the number of cupcakes.

Output

Output T lines, each indicating the minimum possible difference between the length and the width in a rectangular arrangement of the cupcakes.

Constraints

1 ≤ T ≤ 100
1 ≤ N ≤ 108

Example

Input:
4
20
13
8
4

Output:
1
12
2
0

Explanation

Case 1: 20 cupcakes can be arranged in 6 possible ways - 1 x 20, 2 x 10, 4 x 5, 5 x 4, 10 x 2 and 20 x 1. The corresponding differences between the length and the width are 19, 8, 1, 1, 8 and 19 respectively. Hence, 1 is the answer.
Case 4: 4 cupcakes can be arranged as a 2 x 2 square. Difference between the length and the width is 0. You can't do anything better than 0

Problem LinkRESQ

The idea : The idea here is to move from sqrt(number) downward and picking the first number that divides it.

The Code:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        long long int cakes;
        scanf("%lld",&cakes);
        long long int last=sqrt(cakes);
        long long int diff=LLONG_MAX;
        for(long long int i=last;i>=1;i--)
        {
            if(cakes%i==0)
            {
                long long int presentDiff=abs((cakes/i)-i);
                diff=min(diff,presentDiff);
                break;
            }
        }
        cout<<diff<<endl;
    }
    return 0;
}

GCD2

Problem Statement

Frank explained its friend Felman the algorithm of Euclides to calculate the GCD of two numbers. Then Felman implements it algorithm
int gcd(int a, int b)
{
 if (b==0)
  return a;
 else
  return gcd(b,a%b);
}
and it proposes to Frank that makes it but with a little integer and another integer that has up to 250 digits.
Your task is to help Frank programming an efficient code for the challenge of Felman.

Input

The first line of the input file contains a number representing the number of lines to follow. Each line consists of two number A and B (0 <= A <= 40000 and A <= B < 10^250).

Output

Print for each pair (A,B) in the input one integer representing the GCD of A and B.

Example

Input:
2
2 6
10 11


Output:
2
1

Problem Link : GCD2

The idea:  

  • gcd(b,a)=gcd(a,a%b);
  • Now one has to  use the concept of modulo arithmetic. Accept the value of b as string.
  • Extract each digit as dig=b[i]-'0'.
  • Now use rem=((dig*10)%a+b%a)%a;
  • now use ans=gcd(a,rem)
The Code:




#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)
    return a;
    else
    {
        int ans=gcd(b,a%b);
        return ans;
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int a;
        string b;
        cin>>a;
        cin>>b;
        if(a==0)
        {
            cout<<b<<endl;
            continue;
        }
        else
        {
        int rem=0;
        for(int i=0;i<b.length();i++)
        {
            int dig=b[i]-'0';
            rem=((rem*10)%a+dig%a)%a;
        }
        cout<<gcd(a,rem)<<endl;
        }
    }
    
}



Saturday, 19 November 2016

Chef and The Right Triangles

PROBLEM STATEMENT
The Chef is given a list of N triangles. Each triangle is identfied by the coordinates of its three corners in the 2-D cartesian plane. His job is to figure out how many
of the given triangles are right triangles
. A right triangle is a triangle in which one angle is a 90 degree angle. The vertices
of the triangles have integer coordinates and all the triangles given are valid( three points aren't colinear ).  

Input

The first line of the input contains an integer N denoting the number of triangles. Each of the following N
lines contain six space separated integers x1 y1 x2 y2 x3 y3 where (x1, y1),
(x2, y2) and (x3, y3) are the vertices of a triangle.

Output

Output one integer, the number of right triangles among the given triangles.

Constraints

  • 1 ≤ N ≤ 100000 (105)
  • 0 ≤ x1, y1, x2, y2, x3, y3 ≤ 20

Example

Input:
5
0 5 19 5 0 0
17 19 12 16 19 0
5 14 6 13 8 7
0 4 0 14 3 14
0 2 0 14 9 2

Output:
3

PROBLEM LINK:
RIGHTRI


The idea : The idea is to use pythagoras theorem  c^2 = a^2+ b^2 or  2*c^2 = a^2+b^2+c^2 . 
We can do this by creating  a class point and writing a function to calculate difference.

The Code:



#include<iostream>
#include<bits/stdc++.h>
using namespace std;

struct Point
{
    int  x,y;
    Point (int x,int y)
    {
        this->x=x;
        this->y=y;
    }
    
     double   diff(Point &p)
    {
        double  ans= (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y);
        return ans;
    }
    
};

int main()
{
    int T;
    scanf("%d",&T);
    int count=0;
    while(T--)
    {
        int x1,y1,x2,y2,x3,y3;
        scanf("%d %d %d %d %d %d",&x1,&y1,&x2,&y2,&x3,&y3);
        Point p1(x1,y1);
        Point p2(x2,y2);
        Point p3(x3,y3);
        
double  side1=p1.diff(p2);
//cout<<side1<<endl;
double side2=p2.diff(p3);
//cout<<side2<<endl;
double side3=p1.diff(p3);
double hyp=max(side1,side2);
hyp=max(hyp,side3);
if(2*hyp== side1+side2+side3)
count++;
        
    }
    cout<<count<<endl;
    return 0;
}

Chef and Feedback

Problem Statement
Lots of geeky customers visit our chef's restaurant everyday. So, when asked to fill the feedback form, these customers represent the feedback using a binary string (i.e a string that contains only characters '0' and '1'.
Now since chef is not that great in deciphering binary strings, he has decided the following criteria to classify the feedback as Good or Bad : 


If the string contains the substring "010" or "101", then the feedback is Good, else it is Bad. Note that, to beGood it is not necessary to have both of them as substring.


So given some binary strings, you need to output whether according to the chef, the strings are Good orBad.

Input

The first line contains an integer T denoting the number of feedbacks. Each of the next T lines contains a string composed of only '0' and '1'.

Output

For every test case, print in a single line Good or Bad as per the Chef's method of classification.

Constraints

  • ≤ T ≤ 100
  • ≤ |S| ≤ 105


Sum of length of all strings in one test file will not exceed 6*106.


Example

Input:
2
11111110
10101010101010


Output:
Bad
Good



Explanation

Example case 1.

The string doesn't contain 010 or 101 as substrings. 
Example case 2.

The string contains both 010 and 101 as substrings. 

Problem Link : ERROR
The idea : We are trying to use the stl find function . See this Find.
The Code:
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() 
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        string target;
        cin>>target;
        size_t found1=target.find("010");
        size_t found2=target.find("101");
        if(found1==string::npos && found2==string::npos)
        cout<<"Bad"<<endl;
        else
        cout<<"Good"<<endl;
        
    }
return 0;
}




Thursday, 17 November 2016

Maximum K Sums (First Approach)

Problem Statement
Chef likes arrays a lot. Today, he found an array A consisting of N positive integers.
Let L denote the sorted (in non-increasing order) list of size N*(N+1)/2 containing the sums of all possible contiguous subarrays of A. Chef is interested in finding the first K elements from the list L. Can you help him in accomplishing this task?

Input

There is only a single test case per input file.
The first line of input contains two space separated integer numbers N and K denoting the size of the array and the number of the maximal sums you need to find.
The following line contains N space separated integer numbers denoting the array A.

Output

Output K space separated integers where the ith integer denotes the ith element of L.

Constraints

  • 1 ≤ N ≤ 105

  • 1 ≤ K ≤ min(N*(N+1)/2, 105)

  • 1 ≤ Ai ≤ 109

Subtasks

  • Subtask 1 (47 pts) : 1 ≤ N ≤ 1000, 1 ≤ K ≤ min{N*(N+1)/2, 105}
  • Subtask 2 (53 pts) : 1 ≤ N ≤ 105, 1 ≤ K ≤ min{N*(N+1)/2, 105}

Example

Input 1
3 4
1 3 4

Output 1
8 7 4 4

Input 2
3 3
10 2 7

Output 2
19 12 10

Explanation

Test 1:


The first 4 elements of it are [8, 7, 4, 4].


Problem linkKSUM

The idea : Here I will be discussing the brute force approach to solve this problem . This will ensure that you will partially solve the problem . The full solving approach will be discussed in the next post.
The idea is very simple . Generate all sums by simply taking the starting point  'i' as fixed and iterating 'j' right till the end. Now push this in to a vector. Sort it in reverse end by this sort(r.begin(),r.end()) .
Now print these elements.

The Code:
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,k;
    vector<long long int> v;
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)
    {
        int number;
        scanf("%d",&number);
        v.push_back(number);
    }
    vector<long long int> sumArr;
    for(int i=0;i<n;i++)
    {
        long long int sum=0;
        for(int j=i;j<n;j++)
        {
            sum+=v[j];
            sumArr.push_back(sum);
           
        }
    }
    sort(sumArr.rbegin(),sumArr.rend());
    for(int i=0;i<k;i++)
    {
        cout<<sumArr[i]<<" ";
       
    }
    cout<<endl;
   
   
    return 0;
}


Discrepancies in the Voters List

Problem Statement :

As you might remember, the collector of Siruseri had ordered a complete revision of the Voters List. He knew that constructing the list of voters is a difficult task, prone to errors. Some voters may have been away on vacation, others may have moved during the enrollment and so on.
To be as accurate as possible, he entrusted the task to three different officials. Each of them was to independently record the list of voters and send it to the collector. In Siruseri, every one has a ID number and the list would only list the ID numbers of the voters and not their names. The officials were expected to arrange the ID numbers in ascending order in their lists.
On receiving the lists, the Collector realised that there were discrepancies - the three lists were not identical. He decided to go with the majority. That is, he decided to construct the final list including only those ID numbers that appeared in at least 2 out of the 3 lists. For example if the three lists were
23  30  42  57  90
21  23  35  57  90  92
21  23  30  57  90 
then the final list compiled by the collector would be:
21  23  30  57  90
The ID numbers 35, 42 and 92 which appeared in only one list each do not figure in the final list.
Your task is to help the collector by writing a program that produces the final list from the three given lists.
Input format
The first line of the input contains 3 integers N1, N2 and N3. N1 is the number of voters in the first list, N2 is the number of voters in the second list and N3 is the number of voters in the third list. The next N1 lines (lines 2,...,N1+1) contain one positive integer each and describe the first list in ascending order. The following N2 lines (lines N1+2,...,N1+N2+1) describe the second list in ascending order and the final N3lines (lines N1+N2+2,...,N1+N2+N3+1) describe the third list in ascending order.
Output format
The first line of the output should contain a single integer M indicating the number voters in the final list. The next M lines (lines 2,...,M+1) should contain one positive integer each, describing the list of voters in the final list, in ascending order.
Test data
You may assume that 1 ≤ N1,N2,N3 ≤ 50000.
Example
Sample input:
5 6 5
23
30
42
57
90
21 
23 
35 
57 
90 
92 
21 
23 
30 
57 
90 
Sample output:
5
21 
23 
30 
57 
90

Problem Link

VOTERS 
 
 The idea : The idea is pretty simple. Declare an array to be used as map . Count the frequency of each . Now print 
if greater than 2.
 
 
The Code: 
 
 
 #include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n1,n2,n3;
    scanf("%d %d %d",&n1,&n2,&n3);
    int n=n1+n2+n3;
    int k;
    int *mapi=new int[10000001];
    while(n--)
    {
        cin>>k;
        mapi[k]++;
        
    }
    int count=0;
    for(int i=1;i<=10000000;i++)
    {
        if(mapi[i]>=2)
        count++;
    }
    cout<<count<<endl;
    for(int i=1;i<=10000000;i++)
    {
        if(mapi[i]>=2)
        cout<<i<<endl;
    }
    
}

Wednesday, 16 November 2016

Tourist Translations

 Problem Statement

A tourist is visiting Byteland. The tourist knows English very well. The language of Byteland is rather different from English. To be exact it differs in following points:
  • Bytelandian alphabet has the same letters as English one, but possibly different in meaning. Like 'A' in Bytelandian may be 'M' in English. However this does not mean that 'M' in Bytelandian must be 'A' in English. More formally, Bytelindian alphabet is a permutation of English alphabet. It will be given to you and could be any possible permutation. Don't assume any other condition.
  • People of Byteland don't like to use invisible character for separating words. Hence instead of space (' ') they use underscore ('_'). Other punctuation symbols, like '?', '!' remain the same as in English.
The tourist is carrying "The dummies guide to Bytelandian", for translation. The book is serving his purpose nicely. But he is addicted to sharing on BaceFook, and shares his numerous conversations in Byteland on it. The conversations are rather long, and it is quite tedious to translate for his English friends, so he asks you to help him by writing a program to do the same.

Input

The first line of the input contains an integer T, denoting the length of the conversation, and the string M, denoting the English translation of Bytelandian string "abcdefghijklmnopqrstuvwxyz". T and M are separated by exactly one space. Then T lines follow, each containing a Bytelandian sentence S which you should translate into English. See constraints for details.

Output

For each of the sentence in the input, output its English translation on a separate line. Replace each underscores ('_') with a space (' ') in the output. Each punctuation symbol (see below) should remain the same. Note that the uppercase letters in Bytelandian remain uppercase in English, and lowercase letters remain lowercase. See the example and its explanation for clarity.

Constraints

  • 1  T  100
  • M is a permutation of "abcdefghijklmnopqrstuvwxyz"
  • Each sentence is non-empty and contains at most 100 characters
  • Each sentence may contain only lowercase letters ('a'-'z'), uppercase letters ('A'-'Z'), underscores ('_') and punctuation symbols: dot ('.'), comma (','), exclamation ('!'), question-mark('?')

Example

Input:
5 qwertyuiopasdfghjklzxcvbnm
Ph
Pcssi
Bpke_kdc_epclc_jcijsc_mihyo?
Epcf_kdc_liswhyo_EIED_hy_Vimcvpcn_Zkdvp_siyo_viyecle.
Ipp!

Output:
Hi
Hello
What are these people doing?
They are solving TOTR in Codechef March long contest.
Ohh!

Explanation

The string "qwertyuiopasdfghjklzxcvbnm" means that 'a' in Bytelandian is 'q' in English, 'b' in Bytelandian is 'w' in English, 'c' in Bytelandian is 'e' in English and so on.
Thus to translate "Ph" (first sentence in example) to English:
1) We find that 'p' in Bytelandian means 'h' in English. So we replace 'P' with 'H'.
2) Then we see that 'h' in Bytelandian means 'i' in English. So we replace 'h' with 'i'.
3) Therefore, the translation is "Hi".

Problem Link :   TOTR

The Idea :  The idea over here is to use a mapping from one character of code alphabet to english alphabet in code language. Now use this to interconvert.


Problem Code :

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main()
{
    // your code goes here
    int T;
    string code;
    scanf("%d",&T);
    cin>>code;
    map<char,char> Map;
    for(char c='a';c<='z';c++)
    {
        Map[c]=code[c-'a']; // stores the mapping.
    }
    while(T--)
    {
        string ans="";
        string word;
        cin>>word;
        for(int i=0;i<word.length();i++)
        {
            if(islower(word[i]))
            ans+=((char)Map[word[i]]);
            else
            if(isupper(word[i]))
            {
                char c=tolower(word[i]);
                c=Map[c];
                c=toupper(c);
                ans+=c;
               
            }
            else
            if(word[i]=='_')
            {
                ans+=' ';
            }
            else
            ans+='!'
           
        }
        cout<<ans<<endl;
       
       
       
    }

    return 0;
}