A Poem Problem
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.
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
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
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