Chotu and the Lucky Draw

3.6

14 votes
Easy
Problem

It's India vs Pakistan and all the tickets of the match have been sold out. Chotu being a die-hard fan participates in a lucky draw contest to win a ticket to the match.
The Rules of Contest are ->

  • The contest Organizers give a base string B and a lucky number K.
  • There are T rounds.
  • In each round Chotu is given a random string S, Chotu wins the round if the String S is a subsequence of the base String B
  • Chotu wins the ticket to the match if he wins atleast K rounds.

Help Chotu find out if he will win the lucky draw or not.

Note- Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence (A,B,D) is a subsequence of (A,B,C,D,E,F) obtained after removal of elements C, E, and F.



Input
First line of input contains a String B and an integer K.
Next line contains an integer T denoting the number of rounds.
Each of next T lines contain a string S.

Output
Print the number of wins followed by "LUCKY" if Chotu wins the ticket ( number of wins is more than or equal to K) or "UNLUCKY" otherwise (without quotes).
Note - Print number of wins with both "LUCKY" and "UNLUCKY".

Constraints
1 <= |B| <= 105
1 <= |S| <= 105
1 <= T <= 100
1 <= K <= 100

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The string of 1st round ca is not a subsequence of the base string
The string of 2nd round bd is a subsequence of the base string

So total rounds that Chotu win is 1, since the number is equal to the lucky number, so Chotu is lucky for the given draw.

Editor Image

?