Traces

Statement

Goal

You are given an integer t for the number of tests. Each test is a space separated string containing three substrings: base, target, and fixed.

For each test, print true if you can go from base to target by swapping, any amount of times, adjacent letters that are not in the fixed string, or false if you cannot.

Input

Line 1 : An integer t, the number of tests.
Next t lines: A space separated string test containing three substrings: base, target, and fixed.

Output

t lines, each containing the answer true or false to the corresponding test.

Constraints

Every character of base, target and fixed is a lowercase letter of the alphabet.
There are no duplicate characters in fixed
Every character in fixed appears at least once in base and once in target
0 < length(test) < 256

Example

Input

4
race care e
care race e
race care r
race care a

Output

true
true
false
false

Game modes

Fastest, Shortest

Test cases

1. Base rules Test

Input

4 race care e care race e race care r race care a

Output

true true false false

1. Base rules val Validator

Input

4 race care r race care a race care e care race e

Output

false false true true

2. Different lengths Test

Input

4 flat float l bigstring smolstring s ar erase r boyo boy y

Output

false false false false

2. Different lengths val Validator

Input

4 boyo boy y flat float l bigstring smolstring s ar erase r

Output

false false false false

3. Same set Test

Input

4 capes cepas p tanis tansi n alert alter l alerts stelar a

Output

false true true false

3. Same set val Validator

Input

4 capes cepas p alerts stelar a tanis tansi n alert alter l

Output

false false true true

4. >1 letter Test

Input

4 race care ar tanis tansi ta malin calin alin ballots ablltos ls

Output

false true false true

4. >1 letter val Validator

Input

4 tanis tansi ta race care ar ballots ablltos ls malin calin alin

Output

true false true false

5. Edge cases Test

Input

5 abbca abbac b abac acab bc code code code test tset t abcd abdd d

Output

true false true true false

5. Edge cases val Validator

Input

5 code code code abac acab bc abbca abbac b abcd abdd d test tset t

Output

true false true false true

6. Final Test

Input

10 true false e vhmtlstucop vmhtlstucop copls aaaab aaab b bnoykcvqwlvtgz bnoykqvcwlvtgz tgzwk molo oolm l np np p gedsmxbeoikafzjtdlp gesdmxeboikatjzdflp lpikamx aaaaa a a lhjgsmwanlkuod lhjgsmwankulod dngs end end end

Output

false true false true false true true false true true

6. Final val Validator

Input

10 lhjgsmwanlkuod lhjgsmwankulod dngs vhmtlstucop vmhtlstucop copls aaaab aaab b true false e np np p gedsmxbeoikafzjtdlp gesdmxeboikatjzdflp lpikamx aaaaa a a bnoykcvqwlvtgz bnoykqvcwlvtgz tgzwk molo oolm l end end end

Output

true true false false true true false true false true

7. Extra Test

Input

21 abacabb abbcaba c mywwpwoisuvtthhqelgbyypwhxyjdn pywwomwisuqtthehvlgbphxywyyjdn isulgbjdn agaadswffxitttavb aagadswffxitttavb dsxivb deiyysflvljluqbniqqx dyieysfvlljlunbqqiqx sux qqqlnnxvzsssghgiyj nqqlqnxvzghsssgiyj xvziyj roowooianyvccvcjbf woooorianvvcyccjbf ianjbf iwbqbbevhrhvhgnjlrttjy bibwqbegvvhhhrnrjtjlty eny unnnrnzkalaracs unrnnnzkalaracs zkcs qtqlaqqxbfppyrfoillsmllehg ltqqqaqxbfpyrpfoiselllmlhg xboihg pxppnqgggu xpppngggqu nu chhnhhjmkrjjksjz cjhnhhhmrjjkjskz mz dhcvvvvbmwopchpypbqjs vbdcvvvhmwobcphyppqjs mwoqjs qdqqdbecgczo dqqqdbecgczo bezo qbpqbqyddtbdr qbbqqpybtdddr yr wfbfwjtrudxdh fwfjwbtrxuddh th ddvmrjrlmrryfppvpwdo mvddrjmlryrrfpvppdwo jfo zzrznmfffwfausyssoe zrzznmfwfffausssyoe nmauoe zkkiipkiqhxpjvivmgbzsjddeuw iipkikkzqhxpvijvmgbzdjsdeuw qhxmgbeuw qylyshdnnkic yylqshdknnic shic mfmzrtptaxvlvviq mfmzrpttaxvvlviq zraxiq mjjndhazsouogopfbycxxmppngpxlki hmjdjnazsofopguobycpgppmxxnxlki azsbyclki

Output

false true true true true true true true true true true true true true true true true true true true true

7. Extra (val) Validator

Input

21 qqqlnnxvzsssghgiyj nqqlqnxvzghsssgiyj xvziyj qylyshdnnkic yylqshdknnic shic qtqlaqqxbfppyrfoillsmllehg ltqqqaqxbfpyrpfoiselllmlhg xboihg qbpqbqyddtbdr qbbqqpybtdddr yr pxppnqgggu xpppngggqu nu unnnrnzkalaracs unrnnnzkalaracs zkcs roowooianyvccvcjbf woooorianvvcyccjbf ianjbf agaadswffxitttavb aagadswffxitttavb dsxivb chhnhhjmkrjjksjz cjhnhhhmrjjkjskz mz deiyysflvljluqbniqqx dyieysfvlljlunbqqiqx sux iwbqbbevhrhvhgnjlrttjy bibwqbegvvhhhrnrjtjlty eny dhcvvvvbmwopchpypbqjs vbdcvvvhmwobcphyppqjs mwoqjs mjjndhazsouogopfbycxxmppngpxlki hmjdjnazsofopguobycpgppmxxnxlki azsbyclki qdqqdbecgczo dqqqdbecgczo bezo ddvmrjrlmrryfppvpwdo mvddrjmlryrrfpvppdwo jfo mfmzrtptaxvlvviq mfmzrpttaxvvlviq zraxiq zkkiipkiqhxpjvivmgbzsjddeuw iipkikkzqhxpvijvmgbzdjsdeuw qhxmgbeuw mywwpwoisuvtthhqelgbyypwhxyjdn pywwomwisuqtthehvlgbphxywyyjdn isulgbjdn abaacabb abbcaba c zzrznmfffwfausyssoe zrzznmfwfffausssyoe nmauoe wfbfwjtrudxdh fwfjwbtrxuddh th

Output

true true true true true true true true true true true true true true true true true true false true true

8. Very true Test

Input

50 jsjunmoqzjjmmmjgvdwix jjnumsoqzjmmjdgvjmwix oqzwix qoqbquqytfivvvrshfxwfkfld qqqboqyutrivvfsvhwfffklxd thd lytllnmmgvhkoowq ylltlnmgmvhokwoq nhq kxxxpvxqjjxgjajjsvvcveut xxxpxvkqjjjjgjaxsvvveuct qst ezzcxwxwxi ezzcxwxxwi ci ppjilnmgmvbmsgvollvlu ilpjpnbmmvgmsllvgvolu nsu bsgttggvdkrgqgccfceyuztcttbawcipm tggbgsvtdkrgefcgqccyuztwtcctbaipm dkryuzipm evvklmbbbbzxghghoq evvklbmbbbzxhghgoq klzxoq rrjraqqxg rrjraqxqg ag xvwvtvchiysnqcoclpd wvvtxvchiyqocscnlpd hiylpd bonosprhxpvobppicqksenefaezwj ponbsorhxobvipppcqkaneefeszwj rhxcqkzwj iuuupiirwxdnogiiriicbtlhrhicmhkaf ipwriuuiuxdnciiiriogbtlhhmihcrkaf xdnbtlkaf zzszzwofxxxxxrdpi zzzszwofxxrxxxdpi wofdpi lgqnqfvuphppo ngqlqfvpphpuo fo xxrxwyxzxxxxhs xxxrwyxzxxxxhs wyhs rnrocsruzyjyxnkhadwiiig orsrrcnujxyynzkwhiiiadg ukg cdpdxmssssujzg dpdcxmsssujszg xmzg zdddeejhffiuilpiia dzeeddjihffuiiilpa jua ikxiitzehhvnhqcd ixkiitzenvhhhqcd tzeqcd uoqqquugrkpqqmbzyjpjuhva uquuoqqgrkmqqpbzyjpujhva grkbzyhva nnbtegnxcivkbgqqoapntndgnkjws negnntbxciqvgqbkoaptdngnnkjws xcioapjws ifififqarzzzyxne fiiiffqarzyzzxne qarxne czzzzessajbffbv zzczzeassjbffbv ejv mmbmasegenzcjmmp ambmmsngeezmcjmp szp lmlloawhhdtittjkaryayaf lmoallwtitdhhtjyrakyaaf wjf hhxibjmcpppfgklvtthfdn bixhhjmgpcpfpklfttvhdn jmkldn eiameptnzzylwzyykudijjjiyahvx aieemptnyzzzywylkudjjayijihvx ptnkudhvx jqbyqvtiwhsswywjfz jyqvqbtihsywwjwsfz tifz myyekurfyqoyywqgjxyihqynzc myyekurfqyqwyyogjxqiyyhnzc urfgjxnzc llalllfndddwjjyyjys alllllfdddnwjyyjjys fws bhcshsrwufuuuyjunp rcssbhhwfujuunuyup wp ttddqydvuhmciiisykwpznioanncngxf dtqydvdtuhmskcyiiiwpziannnnocgxf uhmwpzgxf kknkxnlgopvpxbte nkknkxlgoppxvbte lgobte hwhwwhnsmsselllalv hwhwhwnsmsselllalv nev ejmeejimejev mejeejimejev iv rgggggzcydmdxbv ggggrgzcymddxbv zcyxbv bbmicrbobbjdlaaeefwh mbbicrbobbjdlaaeefwh icrjdlfwh blxlljzqkddpdrsrvmy jlllbxzqkdrddpsrvmy zqkvmy fyffbfhulndtttgaqxc fhfyffbulngtdttaqxc ulnqxc hzhohoodwfvzzbzphbkiqyrrcxrtnu dhohzoohwfvzzzbbhpkiqrxrrcytnu wfvkiqtnu wiwwoqyikojidpiipigphx wwqwioyiokjidpiphipgix ydx ifqirwxmmmonsjp iifqrwxnmommsjp rwxsjp vyqycvnxosvksth cvqyynvxstsovkh xh ninpnnkxryhyhmsqw npnnnikxryhhymsqw kxrsqw fxzxslgxxgpgviyoyyneq xxfzslxxgggpviyyonyeq slvieq ooloookileeelqhtttotns ooolookieleleqhttttons kiqhns llrxmexppvmpumwvmfmt lxrlmepvxpmpuwvmmfmt eut vbcbnbqgtmbzmwr cbvbnbqgzbtmmwr qgwr kllnlxpbqbbbbm lkllnxqbbbpbbm xm ptsoeorvhjbtdmddafg toeposrvhbmdtdjdafg rvhafg

Output

true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true

8. Very true (val) Validator

Input

50 czzzzessajbffbv zzczzeassjbffbv ejv llalllfndddwjjyyjys alllllfdddnwjyyjjys fws jsjunmoqzjjmmmjgvdwix jjnumsoqzjmmjdgvjmwix oqzwix bhcshsrwufuuuyjunp rcssbhhwfujuunuyup wp xvwvtvchiysnqcoclpd wvvtxvchiyqocscnlpd hiylpd qoqbquqytfivvvrshfxwfkfld qqqboqyutrivvfsvhwfffklxd thd ifqirwxmmmonsjp iifqrwxnmommsjp rwxsjp kxxxpvxqjjxgjajjsvvcveut xxxpxvkqjjjjgjaxsvvveuct qst jqbyqvtiwhsswywjfz jyqvqbtihsywwjwsfz tifz llrxmexppvmpumwvmfmt lxrlmepvxpmpuwvmmfmt eut xxrxwyxzxxxxhs xxxrwyxzxxxxhs wyhs fyffbfhulndtttgaqxc fhfyffbulngtdttaqxc ulnqxc vyqycvnxosvksth cvqyynvxstsovkh xh mmbmasegenzcjmmp ambmmsngeezmcjmp szp zzszzwofxxxxxrdpi zzzszwofxxrxxxdpi wofdpi lgqnqfvuphppo ngqlqfvpphpuo fo rgggggzcydmdxbv ggggrgzcymddxbv zcyxbv nnbtegnxcivkbgqqoapntndgnkjws negnntbxciqvgqbkoaptdngnnkjws xcioapjws lmlloawhhdtittjkaryayaf lmoallwtitdhhtjyrakyaaf wjf bsgttggvdkrgqgccfceyuztcttbawcipm tggbgsvtdkrgefcgqccyuztwtcctbaipm dkryuzipm ifififqarzzzyxne fiiiffqarzyzzxne qarxne kknkxnlgopvpxbte nkknkxlgoppxvbte lgobte iuuupiirwxdnogiiriicbtlhrhicmhkaf ipwriuuiuxdnciiiriogbtlhhmihcrkaf xdnbtlkaf uoqqquugrkpqqmbzyjpjuhva uquuoqqgrkmqqpbzyjpujhva grkbzyhva evvklmbbbbzxghghoq evvklbmbbbzxhghgoq klzxoq rrjraqqxg rrjraqxqg ag blxlljzqkddpdrsrvmy jlllbxzqkdrddpsrvmy zqkvmy wiwwoqyikojidpiipigphx wwqwioyiokjidpiphipgix ydx ppjilnmgmvbmsgvollvlu ilpjpnbmmvgmsllvgvolu nsu fxzxslgxxgpgviyoyyneq xxfzslxxgggpviyyonyeq slvieq eiameptnzzylwzyykudijjjiyahvx aieemptnyzzzywylkudjjayijihvx ptnkudhvx ejmeejimejev mejeejimejev iv hhxibjmcpppfgklvtthfdn bixhhjmgpcpfpklfttvhdn jmkldn ttddqydvuhmciiisykwpznioanncngxf dtqydvdtuhmskcyiiiwpziannnnocgxf uhmwpzgxf cdpdxmssssujzg dpdcxmsssujszg xmzg kllnlxpbqbbbbm lkllnxqbbbpbbm xm hwhwwhnsmsselllalv hwhwhwnsmsselllalv nev zdddeejhffiuilpiia dzeeddjihffuiiilpa jua bonosprhxpvobppicqksenefaezwj ponbsorhxobvipppcqkaneefeszwj rhxcqkzwj myyekurfyqoyywqgjxyihqynzc myyekurfqyqwyyogjxqiyyhnzc urfgjxnzc hzhohoodwfvzzbzphbkiqyrrcxrtnu dhohzoohwfvzzzbbhpkiqrxrrcytnu wfvkiqtnu ezzcxwxwxi ezzcxwxxwi ci lytllnmmgvhkoowq ylltlnmgmvhokwoq nhq ptsoeorvhjbtdmddafg toeposrvhbmdtdjdafg rvhafg ikxiitzehhvnhqcd ixkiitzenvhhhqcd tzeqcd vbcbnbqgtmbzmwr cbvbnbqgzbtmmwr qgwr ninpnnkxryhyhmsqw npnnnikxryhhymsqw kxrsqw rnrocsruzyjyxnkhadwiiig orsrrcnujxyynzkwhiiiadg ukg ooloookileeelqhtttotns ooolookieleleqhttttons kiqhns bbmicrbobbjdlaaeefwh mbbicrbobbjdlaaeefwh icrjdlfwh

Output

Solution language

Solution

Stub generator input