## A Poem Problem

Points: 1
Time limit: 3.0s
Memory limit: 512M

Authors:
Problem type
Allowed languages

The cipher's key consists of a set of rules. Each rule is a pair of letters mapping the first letter to a second letter in the encrypted string. No character will be mapped (appear as the first letter) more than once, and all characters in a rule will be uppercase English letters. Characters not appearing in a rule should not be changed in the encrypted string. The final step of your plain is to create a program that can both encrypt and decrypt the hidden poems.

#### Input Specification

The input begins with two lines. The first line contains a single integer $$N$$ ($$1\leq N\leq 26$$) the numbers of rules in the cipher. The second line contains a single integer $$M$$ ($$1\leq M \leq 300$$), the number of lines to encrypted or decrypt respectively. Following this will be $$N$$ lines, each containing two uppercase English characters which define a rule. Then, there will be $$M$$ lines, each containing two strings. The first string will be either E or D, which corresponds to encrypt and decrypt respectively. The second string should be either encrypted or decrypted, and will consist of between 1 and 1000 characters inclusive, each of which will be either an uppercase English letter or the underscore character _.

#### Output Specification

Display $$M$$ lines containing the encrypted or decrypted strings.

#### Sample Input 1

2
3
A B
B A
E ABC
E ABCABCABC
D BACBACBAC

#### Sample Output 1

BAC
BACBACBAC
ABCABCABC

#### Sample Input 2

23
29
S Q
T K
J E
U A
H Z
R W
E X
B M
O Y
V S
Y B
Q V
K J
M U
L D
D F
X L
W R
Z P
P I
I T
A O
F H
D KBGXW_KBGXW_MAWNTNG_MWTGZK
D TN_KZX_HYWXQKQ_YH_KZX_NTGZK
D RZOK_TUUYWKOD_ZONF_YW_XBX
D _
D TN_RZOK_FTQKONK_FXXIQ_YW_QJTXQ
D MAWNK_KZX_HTWX_YH_KZTNX_XBXQ
D YN_RZOK_RTNGQ_FOWX_ZX_OQITWX
D RZOK_KZX_ZONF_FOWX_QXTPX_KZX_HTWX
D _
D ONF_RZXN_KZB_ZXOWK_MXGON_KY_MXOK
D RZOK_FWXOF_ZONF_RZOK_FWXOF_HXXK
D _
D RZOK_KZX_ZOUUXW_RZOK_KZX_CZOTN
D TN_RZOK_HAWNOCX_ROQ_KZB_MWOTN
D RZOK_KZX_ONSTD_RZOK_FWXOF_GWOQI
D FOWX_TKQ_FXOFDB_KXWWYWQ_CDOQI
D _
D RZXN_KZX_QKOWQ_KZWXR_FYRN_KZXTW_QIXOWQ
D ONF_ROKXWF_ZXOSXN_RTKZ_KZXTW_KXOWQ
D FTF_ZX_QUTDX_ZTQ_RYWJ_KY_QXX
D FTF_ZX_RZY_UOFX_KZX_DOUM_UOJX_KZXX
D _
D KBGXW_KBGXW_MAWNTNG_MWTGZK
D TN_KZX_HYWXQKQ_YH_KZX_NTGZK
D RZOK_TUUYWKOD_ZONF_YW_XBX
D FOWX_HWOUX_KZB_HXOWHAD_QBUUXKWB

#### Sample Output 2

TYGER_TYGER_BURNING_BRIGHT
IN_THE_FORESTS_OF_THE_NIGHT
WHAT_IMMORTAL_HAND_OR_EYE
COULD_FRAME_THY_FEARFUL_SYMMETRY
_
IN_WHAT_DISTANT_DEEPS_OR_SKIES
BURNT_THE_FIRE_OF_THINE_EYES
ON_WHAT_WINGS_DARE_HE_ASPIRE
WHAT_THE_HAND_DARE_SEIZE_THE_FIRE
_
AND_WHAT_SHOULDER_WHAT_ART
COULD_TWIST_THE_SINEWS_OF_THY_HEART
AND_WHEN_THY_HEART_BEGAN_TO_BEAT
_
WHAT_THE_HAMMER_WHAT_THE_CHAIN
IN_WHAT_FURNACE_WAS_THY_BRAIN
_
WHEN_THE_STARS_THREW_DOWN_THEIR_SPEARS
AND_WATERD_HEAVEN_WITH_THEIR_TEARS
DID_HE_SMILE_HIS_WORK_TO_SEE
_
TYGER_TYGER_BURNING_BRIGHT
IN_THE_FORESTS_OF_THE_NIGHT
WHAT_IMMORTAL_HAND_OR_EYE
DARE_FRAME_THY_FEARFUL_SYMMETRY

#### Sample Input 3

17
14
C K
M C
R O
J A
H M
Q H
N P
P N
I E
A G
O I
K R
G J
D Q
E F
F L
L D
E I_MET_A_TRAVELLER_FROM_AN_ANTIQUE_LAND
E WHO_SAID_TWO_VAST_AND_TRUNKLESS_LEGS_OF_STONE
E STAND_IN_THE_DESERT_NEAR_THEM_ON_THE_SAND
E HALF_SUNK_A_SHATTERD_VISAGE_LIES_WHOSE_FROWN
E AND_WRINKLED_LIP_AND_SNEER_OF_COLD_COMMAND
E WHICH_YET_SURVIVE_STAMPD_ON_THESE_LIFELESS_THINGS
E THE_HAND_THAT_MOCKD_THEM_AND_THE_HEART_THAT_FED
E AND_ON_THE_PEDESTAL_THESE_WORDS_APPEAR
E MY_NAME_IS_GOZZYMANDIAS_KING_OF_KINGS
E LOOK_ON_MY_WORKS_YE_MIGHTY_AND_DESPAIR
E NOTHING_BESIDE_REMAINS_ROUND_THE_DECAY
E OF_THAT_COLOSSAL_WRECK_BOUNDLESS_AND_BARE
E THE_LONE_AND_LEVEL_SANDS_STRETCH_FAR_AWAY

#### Sample Output 3

E_CFT_G_TOGVFDDFO_LOIC_GP_GPTEHUF_DGPQ
WMI_SGEQ_TWI_VGST_GPQ_TOUPRDFSS_DFJS_IL_STIPF
STGPQ_EP_TMF_QFSFOT_PFGO_TMFC_IP_TMF_SGPQ
MGDL_SUPR_G_SMGTTFOQ_VESGJF_DEFS_WMISF_LOIWP
GPQ_WOEPRDFQ_DEN_GPQ_SPFFO_IL_KIDQ_KICCGPQ
TFDD_TMGT_ETS_SKUDNTIO_WFDD_TMISF_NGSSEIPS_OFGQ
WMEKM_YFT_SUOVEVF_STGCNQ_IP_TMFSF_DELFDFSS_TMEPJS
TMF_MGPQ_TMGT_CIKRQ_TMFC_GPQ_TMF_MFGOT_TMGT_LFQ
GPQ_IP_TMF_NFQFSTGD_TMFSF_WIOQS_GNNFGO
CY_PGCF_ES_JIZZYCGPQEGS_REPJ_IL_REPJS
DIIR_IP_CY_WIORS_YF_CEJMTY_GPQ_QFSNGEO
PITMEPJ_BFSEQF_OFCGEPS_OIUPQ_TMF_QFKGY
IL_TMGT_KIDISSGD_WOFKR_BIUPQDFSS_GPQ_BGOF
TMF_DIPF_GPQ_DFVFD_SGPQS_STOFTKM_LGO_GWGY