Baidu, Inc. is a Chinese Web services company. Among the services they provide are web search and "Baidu Baike", a virtual, collaborative encyclopedia. Due to its remarkable growth and interesting set of challenges its employees need to solve on a daily basis, many young programmers aspire to get a internships or even full-time jobs at this company.
Emi "the Retired" Shouko will travel to Beijing next year and would like to get an interview there for an internship. He is now reading some books with common coding interview questions. He is especially interested in problems related to web search. One of the problems that has been drawing Emi's attention is as follows.
Given an N-character text and an M-character pattern, we would like to know if it is possible to find the pattern in the text. However, the pattern does not need to occur exactly. The search allows a maximum of K mismatches, where a mismatch can be any of the following: a substitution, an insertion, or the removal of a character.
Emi really liked this problem. He has had an idea and started coding his solution furiously. He knows you would love to join him for his trip to Beijing, so he wishes you to solve this problem as well.
The first row of the input has the integers M, N, and K. The second row contains a pattern made of M characters from '_a_' to '_z_'. The third row contains a text made of N characters from '_a_' to '_z_'.
If the pattern occurs in the text with at most K mismatches, print "S" (without the double quotes). Otherwise, print "N" (without the double quotes).
In the first example, if we remove the character '_b_' and replace '_c_' with '_e_', the resulting text will be "_aedef_", which contains the pattern "_aed_". The same cannot be said if the maximum numbers of allowed mismatches were 1.
## Input
The first row of the input has the integers M, N, and K. The second row contains a pattern made of M characters from '_a_' to '_z_'. The third row contains a text made of N characters from '_a_' to '_z_'. 1 ≤ M ≤ 102 1 ≤ N ≤ 106 1 ≤ K ≤ 20
## Output
If the pattern occurs in the text with at most K mismatches, print "S" (without the double quotes). Otherwise, print "N" (without the double quotes).
[samples]
## Note
In the first example, if we remove the character '_b_' and replace '_c_' with '_e_', the resulting text will be "_aedef_", which contains the pattern "_aed_". The same cannot be said if the maximum numbers of allowed mismatches were 1.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ N_k \in \mathbb{Z} $ be the number of nodes, $ M_k \in \mathbb{Z} $ the number of edges.
- Let $ G_k = (V_k, E_k) $ be a directed weighted graph with $ V_k = \{1, 2, \dots, N_k\} $ and $ E_k \subseteq V_k \times V_k \times \mathbb{R} $.
- Each edge $ (u, v, c) \in E_k $ denotes a directed edge from $ u $ to $ v $ with weight $ c $.
Let $ F_k(u, v) $ denote the shortest path weight from node $ u $ to node $ v $ in $ G_k $, defined as the minimum sum of edge weights over all paths from $ u $ to $ v $, and $ F_k(u, v) = \infty $ if no such path exists.
**Constraints**
1. $ 1 \le T \le 100 $
2. For each test case $ k $:
- $ 2 \le N_k \le 2000 $
- $ 1 \le M_k \le 5000 $
- For each edge $ (u, v, c) \in E_k $: $ 1 \le u, v \le N_k $, $ u \ne v $, $ -10^6 \le c \le 10^6 $
- Multiple edges between same $ (u, v) $ are allowed.
**Objective**
For each test case $ k $, compute:
$$
\min_{\substack{u, v \in V_k \\ u \ne v}} F_k(u, v)
$$
If this minimum is $ -\infty $ (i.e., there exists a negative cycle reachable from some $ u $ and from which $ v $ is reachable, with $ u \ne v $), output "-inf". Otherwise, output the finite minimum value.