I. I don't have the name I was supposed to have
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Problem B — Bad Latex from 2026 ICPC Gran Premio de Mexico - Primera Fecha had some trouble with its testcases. Apparently, the input format didn't specify correctly the format restrictions on the testdata and contestants ended up very confused about it.

This time, you will help Racsó by coding a validator for the currently generated test cases. The restrictions Racsó set up so that the problem becomes easy to solve are the following:

  • The test data will only consist of letters (could be in lowercase or uppercase), digits, spaces and the special symbols !?.,;$#^{}_=+*.
  • There won't be any leading or trailing space in the lines of the test data.
  • All subscripts and superscripts will appear with integers with the exact format X_{Y} or X^{Y} (where $$$X$$$ is either an integer or an alphanumeric string and $$$Y$$$ is an integer) and they will not be nested. These should be the only possible structures in which characters _^{} appear.
  • In addition, every digit is surrounded by other digits, letters or spaces, with the subscripts/superscripts being the only exception to this.
  • Numbers won't have leading zeros.
  • There are no consecutive spaces.
  • If a line ends with an integer and the next one starts with an integer, these two are not part of the same value.

Can you handle these test cases?

Input

The first line of input contains an integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — The number of lines of the test case.

The following $$$n$$$ lines contain a string $$$s_{i}$$$ ($$$1 \leq |s_{i}| \leq 1000$$$) — The $$$i$$$-th line contains the contents of the $$$i$$$-th line of the test case.

It is guaranteed that all $$$s_{i}$$$ consists of printable ASCII characters (codes in range $$$[32, 126]$$$).

Output

Print a single line — "Ok" if the test case is valid or "Validation failed" otherwise.

Examples
Input
4
This example shows a value
Of 1000000000 without being compressed to 10^{9}
Which is annoying when read. $ S_{10} = 2^{100000} + 780000 $
My ID is RA180000 but that was back in the year 20000
Output
Ok
Input
3
This example should show
An incorrect test case since 100.10^{1000}
Should not be correct.
Output
Validation failed
Input
2
Another simple example with multiple incorrect braces
$$ 10^{100} = 10 {14} $$
Output
Validation failed
Input
1
$ 100^{2x + 1} $ should not be possible
Output
Validation failed
Input
1
  Leading and Trailing
Output
Validation failed
Input
2
Hey, this one looks like it is not valid.
However, it is even if it contains a single 0
Output
Ok
Input
1
Hello,  this has two  consecutive spaces.
Output
Validation failed
Input
1
Wait, is 000 valid?
Output
Validation failed
Input
1
No nested $ X_{10_{11}} $ allowed!
Output
Validation failed
Input
1
My email is johndoe@email.com
Output
Validation failed