The year is 2025, 4 years since the ruler of Earth, the benevolent MAX, came into power and outlawed all forms of pointless self-expression. Since the fall of the decadent, sinful old-world, you have kept your head down and worked your way into the office of the supreme leader of the world. Years of effort has come to this opportunity. Your dastardly plot will doubtlessly get you killed, or worse, if you are ever discovered, but you consider this a small price to pay. Your aim is to send your favourite poems to your friends around the world by hiding them in the daily propaganda broadcast from the leader's own office. The message will be hidden using a simple cipher in which each letter may be replaced with another.

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 CYADF_HWOUX_KZB_HXOWHAD_QBUUXKWB
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_RZOK_QZYADFXW_RZOK_OWK
D CYADF_KRTQK_KZX_QTNXRQ_YH_KZB_ZXOWK
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_DREAD_HAND_WHAT_DREAD_FEET
_
WHAT_THE_HAMMER_WHAT_THE_CHAIN
IN_WHAT_FURNACE_WAS_THY_BRAIN
WHAT_THE_ANVIL_WHAT_DREAD_GRASP
DARE_ITS_DEADLY_TERRORS_CLASP
_
WHEN_THE_STARS_THREW_DOWN_THEIR_SPEARS
AND_WATERD_HEAVEN_WITH_THEIR_TEARS
DID_HE_SMILE_HIS_WORK_TO_SEE
DID_HE_WHO_MADE_THE_LAMB_MAKE_THEE
_
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 TELL_THAT_ITS_SCULPTOR_WELL_THOSE_PASSIONS_READ
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