G. Good as Gold
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Cindy has been having fun with the video game that Alice recommended, Pokey Mans: I'm in Pain, but with the 'S'. Sure the game feels rushed, and it has a host of bugs and glitches and other technical problems that are quite frankly embarrassing for a franchise as large as Pokey Mans... but underneath all that garbage is a game that Cindy finds to be genuinely fun! It's just... a lot of garbage...

Cindy is a very competitive player, so she wants to unlock the incredibly powerful character, Golden Joseph, affectionately known as Golden Joe. Golden Joe will only join your team after you've acquired at least $$$x$$$ Joe-Bucks from exploring the world.

You get Joe-Bucks by finding Joe's secret treasure chests. There are $$$n$$$ different treasure chests whose locations are scattered throughout the map. Each treasure chest gives Cindy some Joe-Bucks when opened, but this amount is not fixed.

Each treasure chest has its own drop table, which is some list of $$$k$$$ non-negative integers. When you open some treasure chest, the game uniformly randomly selects one of the $$$k$$$ values from its drop table, and then gives you that many Joe-Bucks. Cindy can open as many treasure chests as she wants, but once opened, the treasure chest then disappears and cannot be opened again.

These treasures eventually respawn, but it takes a long time and Cindy is impatient. So, right now, with these $$$n$$$ chests, help answer Cindy's question: Is it possible for her to get enough Joe-Bucks to unlock Golden Joe? And if so, is it guaranteed? Or does she have to get lucky?

Input

The first line of input contains three space-separated positive integers $$$n$$$, $$$k$$$, and $$$x$$$.

Then, $$$n$$$ lines follow, each describing the drop table of a treasure chest. Each drop table is described by a line containing $$$k$$$ space-separated integers, the contents of this drop table.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq x \leq 10^{9} \\ 1 \leq n, k \\ nk \leq 10^5 \\ \text{The values in the drop table are positive integers not greater than $10^8$.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{33} & k = 1 \\ \hline 2 & \mathbf{33} & nk \leq 20 \\ \hline 3 & \mathbf{34} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Output
  • If it is certain that Cindy can get at least $$$x$$$ Joe-Bucks by opening treasure chests, no matter her luck, output ALWAYS
  • If it is possible but not guaranteed to get at least $$$x$$$ Joe-Bucks by opening treasure chests, output SOMETIMES
  • If it is impossible to get at least $$$x$$$ Joe-Bucks by opening treasure chests, output NEVER
Examples
Input
3 4 5
3 1 4 1
5 9 2 6
5 3 5 8
Output
ALWAYS
Input
5 2 10
1 100000000
1 100000000
1 100000000
1 100000000
1 100000000
Output
SOMETIMES
Input
1 1 2
1
Output
NEVER
Input
1 6 999
30 50 10 100 200 777
Output
NEVER