FINGP - Fingerprints

Professor Emad Eldin one of the best people in pattern recognition, he asked his students to create a program to check if a special pattern belongs to fingerprints of someone or not.

He said that we can consider that a computer reads the special pattern and the fingerprints as strings, and we can say that the special pattern belongs to the fingerprint if the last substring of the fingerprint string is the same as the special pattern string.

Your task is to help professor Emad students.

Input

The first line of the input contains special pattern string S (1 ≤ |S| ≤ 50). Second line will be a single integer N, the number of fingerprints (1 ≤ N ≤ 10). N lines follow, each line contains fingerprint string F (1 ≤ |F| ≤ 50).

Output

For each test case, print an integer K, the number of fingerprints strings that special pattern string belongs to it. Followed by K lines, each contains the fingerprint string that the special pattern string belongs to it. You should print the fingerprint strings in a lexicographical order. If there is no fingerprint belongs to the special pattern, print "Wrong fingerprints!" instead.

Examples

Input:
On
5
Pattern recognatiOn
CommOn patterN
game
organizatiOn
lion

Output:
2
Pattern recognatiOn
organizatiOn
Input:
Ze
2
Fingerprint
pattern design

Output:
Wrong fingerprints!

Notes

  • String S contains uppercase English letters ('A' - 'Z') and lowercase English letters ('a' - 'z') only.
  • All other strings in the input contains uppercase English letters ('A' - 'Z'), lowercase English letters ('a' - 'z') and spaces (' ') only.
  • All strings are case sensitive ('A' is not equal to 'a').
  • Lexicographical order is defined in following way. When we compare s and t, first we find the leftmost position with differing characters: si ≠ ti. If there is no such position (i.e. s is a prefix of t or vice versa) the shortest string is less. Otherwise, we compare characters si and ti according to their order in alphabet.

Added by:atef
Date:2015-04-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: MAWK BC C-CLANG NCSHARP CPP14-CLANG COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA

hide comments
2015-05-23 16:02:06 shubhankaryash
AC :). The problem statement says string max size is 50 but i made it to 100 and got ac

Last edit: 2015-05-23 16:08:45
2015-05-23 05:03:27
is output "Wrong fingerprints!" or "Wrong fingerprints!\n" ? Also make it clear for last string of first output.
2015-05-19 05:55:19 :.Mohib.:
I think my solution is correct.... can u check it plzz....@atef
2015-05-12 23:50:47 Nick
The ordering is basically the default comparator used for strings in languages like Python and C++ (case sensitive), isn't it? How to deal with spaces?
2015-05-08 13:24:28 atef
adheen this will help you http://en.wikipedia.org/wiki/Lexicographical_order
2015-05-08 03:55:42
Can anyone please explain it: 'When we compare s and t, first we find the leftmost position with differing characters: si ≠ ti. If there is no such position (i. e. s is a prefix of t or vice versa) the shortest string is less. Otherwise, we compare characters si and ti according to their order in alphabet.'
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.