LOVEGURU - Love Guru

Recently after girls being allowed to get admitted into IUT, the number of couples in IUT (International University Of Technology) is gradually increasing. In last few months a problem has been noticed. More than one boy/girl had crush on same boy/girl. These created conflicts amongst students. To solve this problem, IUTRC (IUT Relationship Community) came up with a solution. They set up rules with whom a student can only get in a relationship. If your name and the other persons name has a common substring of length k, only then can you engage yourselves in a relationship. Now, as a Love Guru, students are coming to you for knowing if his relationship with his crush possible or not. Help them Love Guru.

Input

First line contains two integer 0 < n < 10000 and 1 < k < = 100. It is guaranteed than n*m doesn't exceed 106.

n refers the number of people came for your help and k refers the minimum common substring size.

Then next n lines contains two space separated strings each containing only lower case letters. Name of the boy and name of the girl. No name contains fewer than 2 characters or more than 100 characters.

Output

For each case on each line print "Yes" if possible and "No" otherwise.

Example

Input:
4 3
salman almiza
rizvi krizvia
abid nowmi
atondro iroboton

Output:
Yes
Yes
No
Yes

Added by:Safayet
Date:2018-11-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2020-10-13 07:52:00
Done in O(n*m)
2018-12-14 15:06:46
Never use printf/scanf and cin/cout together, leads to unnecessary WAs
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.