Question

You are provided with a large string and one or more small strings. You need to find if the large string can be formed by combining all the small strings. You can interchange characters of small strings internally and you can combine small strings in any order. Print "YES" if it is possible, otherwise print "NO". Note: All strings contain lower case alphabets only.

Answer 1

Answer:

In python 3 modify your input by removing # if u know what i mean

Explanation:

"""You are provided with a large string and one or more small strings. You need to find if the large string can be formed by combining all the small strings. You can interchange characters of small strings internally and you can combine small strings in any order. Print "YES" if it is possible, otherwise print "NO".

Note: All strings contain lower case alphabets only.

Constraints

1 <= length of large string <= 500000

1 <= length of small string <= 1000

1 <= N <= 500

Input

First line contains the large string

Second line contains an integer N denoting total number of small strings

Next N lines contain strings smaller than large string

Output

Print single line with YES or NO

Time Limit

1

Examples

Example 1

Input

dogisaloyalanimal

5

a

alloy

is

god

lamina

Output

YES

Explanation :

Large string is "dogisaloyalanimal". There are 5 small strings — "a", "alloy", "is", "god", "lamina". We can do following operations on small strings:

Interchange characters of "alloy" to form "loyal".

Interchange characters of "god" to form "dog".

Interchange characters of "lamina" to form "animal".

So, we formed new set of small strings — "a", "loyal", "is", "dog", "animal". Now combine small strings in the below order:

"dog" + "is" + "a" + "loyal" + "animal"

We got it combined as "dogisaloyalanimal". This is same as large string provided. So, the output is "YES".

Example 2

Input

thisisgood

4

god

is

so

hit

Output

NO

Explanation:

Large string is "thisisgood". There are 4 small strings — "god", "is", "so", "hit". We cannot form the large string by combining small strings even after interchanging its characters internally. So, the output is "NO".

"""

#########################################################################################################################################################################################################################

from itertools import permutations as per

############################################################

#input1 = "dogisaloyalanimal"

#found = input1.find('god')

#print(found)

############[Default input]###################################

#items = ["a","alloy","is","god","lamina"]

#given = "dogisaloyalanimal"

items = ["god","is","so","hit"]

given = "thisisgood"

#############################################################

count = 0

#print(len(items))

for item in range(0,len(items)):

   #print(items[item])

   temp_per = [''.join(p) for p in per(items[item])]

   #print(temp_per,"Temp_pre")

   for pre_temp in temp_per:

       #print(pre_temp,"pre_temp")

       

       if pre_temp in given:

           count+=1

           #print(temp_per[0],"found")

           #print(count)

           break

if count==len(items):

   #print("This ",items,"can be made")

   print("Yes")

else:

   #print("This ",items,"can not be made from ",given)

   print("No")

#############[Debug codes]#####################################    

       #else:

           #print(temp_per[0],"Not found")

           #break

   #if given in temp_per:

   #    print(temp_per,"found")

   #else:

   #    print("Not found")

   #    #break

   #print("Loop")

   #print (temp_per)

# Function to find permutations of a given string

#result = [values[0] + i + j for i in values for j in values]