题目描述

昨天yq晚上看到室友在玩一个叫彩虹六号的游戏，yq就好奇的凑上去看了下。她好像在玩一个可以扔炸药的角色，于是yq凑上去和他分享，yq说「原神里也有会扔炸药的，比你这个好看多了」。 yq的室友让她闭嘴，别影响她打游戏。yq想了想的确，影响别人打游戏是不好的，于是她就不说话了。 后来室友换了个叫DOC的角色，好像还能给队友回血，yq看到了这是真的忍不住了。yq立刻手机打开了原神，冲上去和室友说到「原神里也有好多能给队友回血的角色诶」，说着将手机拿过去想给她看看... 不知道这家伙是不是因为被对面打烂了，就火气很大，在这时唰的一下站了起来，用手不礼貌的指着yq的脸大喊，能不能别用你那破原神影响我。yq听着她的话感到一阵羞辱，我好心和他分享，他却如此这般。 想着这样自私的室友，yq也就没了和她争吵的念头，yq就回自己的座位去了。随后yq只是在位子上嘀咕着，米黑是这样的，她就跟火药桶被点炸了一样，立刻冲过来夺了yq的手机。很是吓人。她假装义正言辞的跟我说，让yq别拿原神这种游戏来恶心他。yq低着头一眼不发，舍友也渐渐放下了持着手机的手臂。 僵持了半分钟，舍友说她平时说话糙了点，但是对人一直很友善，刚刚咖啡馆打输了才这么冲动，希望yq别生气。yq一时无言以对，就说道「没事，原神里优菈也是...」 yq话还没说完，她青筋又暴起来，一下子把yq的手机摔在了地上... 说真的，现在yq才认清室友自私自利的嘴脸，根本不值得yq给他分享好东西

yq在认清舍友的真正面目后决定换一个舍友，为了有一个和谐的环境和共同的话题。yq希望舍友也是一个原批，于是yq开始挑选舍友，yq认为原批的身份ID号会不一样。 身份ID号有以下规律

• ID的长度应该正好是m；
• ID应该只由0到9的数字组成；
• 原批的ID不应出现在ID数据库（以字符串s给出中子序列（不一定是连续的）。

yq找出了两个长度为m的字符串：l和r，都只由0到9的数字组成。他认为ID中的第i位数字在l和r之间，才会是原批。

输入格式

第一行包含一个整数t（1≤t≤10000）--测试用例的数量。

每个测试案例的第一行包含一个字符串s（1≤|s|≤300000），仅由0到9的数字组成--ID数据库。

第二行包含一个单一的整数m（1≤m≤10）--密码的要求长度。

第三行包含一个字符串l（|l|=m），仅由0到9中的数字组成--每个数字的下限值。

第四行包含一个字符串r（|r|=m），仅由0到9中的数字组成--对每个数字的上限限制，为所有i从1到m

所有测试案例中s的长度之和不超过300000

输出格式

对于每个测试案例，如果存在一个符合所有标准的ID，则存在原批打印 "YES"。否则打印 "NO"。

样例

输入

5
88005553535123456
2
50
56
123412341234
3
111
444
1234
4
4321
4321
459
2
49
59
00010
2
10
11

输出

YES
NO
YES
NO
YES

样例提示

在第一个测试案例中，yq可以选择ID为 "50"。他并没有作为子序列出现在s中，所以是原批。

在第二个测试案例中，所有三个数字的组合，每个都是从1到4，符合l和r的标准。然而，他们都作为子序列出现在s中。例如，"314 "出现在[3,5,12]位，"222 "出现在**[2,6,10]位，所以不是原批。

在第三个测试案例中，yq可以选择密码 "4321"。实际上，这是唯一符合l和r上标准的ID。幸运的是，他并没有作为子序列出现在s中。

在第四个测试案例中，只有 "49 "和 "59 "符合l和r的标准。他们都作为子序列出现在s中。

在第五个测试案例中，yq可以选择ID "11"。