D. TL, ML or OK?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Important:

  • This problem contains very simplified information about what happens in real life.
  • The values specified in the statement are approximate.
  • In a real situation, the calculations may be much more complex and depend on more details.

Artistic problem statement

Aidar finally finished writing the solution to the problem — he was confident in its correctness but doubted its efficiency.

Aidar's solution worked as follows: on each of the $$$n$$$ iterations of the loop, it performed $$$q$$$ calculations and added $$$k$$$ integers to the data structure.

Before submitting to the system, Aidar decided to show the final code to his teammates and ask for their opinions:

  • Begimai said that the solution performs too many calculations — and therefore will not fit within the time limit.
  • Viktor noted that the solution adds too many integers to the data structure — and therefore will not fit within the memory limit.
  • Aidar himself still hoped that the team's estimates were too pessimistic and that the solution would pass all tests successfully.

Based on the available information about Aidar's solution, determine what verdict it will receive.

Fixed values used in the problem

It is known that in the problem Aidar is solving, the limits are set to $$$1$$$ second and $$$256$$$ megabytes.

  • The number of operations that the language can perform in $$$1$$$ second:
    • C++: $$$5 \cdot 10^8$$$;
    • Java: $$$10^8$$$;
    • Python: $$$2 \cdot 10^7$$$.
  • The number of integers that can fit in $$$256$$$ megabytes: $$$2 \cdot 10^7$$$.
  • Adding to the data structure takes $$$5$$$ operations.
  • A calculation takes $$$2$$$ operations.
Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ — the number of iterations of the loop in Aidar's solution.

The second line contains an integer $$$q$$$ $$$(0 \le q \le 10^6)$$$ — the number of calculations performed on each iteration of the loop.

The third line contains an integer $$$k$$$ $$$(0 \le k \le 10^6)$$$ — the number of integers added to the data structure on each iteration of the loop.

The fourth line contains a string $$$L$$$, denoting the programming language used for the solution:

  • $$$L$$$ is equal to cpp if Aidar wrote the solution in C++.
  • $$$L$$$ is equal to java if Aidar wrote the solution in Java.
  • $$$L$$$ is equal to py if Aidar wrote the solution in Python.
Output

In a single line, output the string $$$V$$$, denoting the expected verdict:

  • $$$V$$$ should be equal to OK if the solution does not exceed any of the problem limits.
  • $$$V$$$ should be equal to TL if the solution exceeds the time limit but does not exceed the memory limit.
  • $$$V$$$ should be equal to ML if the solution exceeds the memory limit but does not exceed the time limit.
  • $$$V$$$ should be equal to TL and ML if the solution exceeds both limits.
Examples
Input
20000
2000
200
java
Output
OK
Input
100000
0
300
cpp
Output
ML
Input
1000000
1000000
0
py
Output
TL
Input
1000000
2000
200
java
Output
TL and ML
Note

First test example

Aidar wrote the solution to the problem in Java.

In total, the solution will perform $$$2 \cdot 10^4$$$ iterations, on each of which:

  • it will perform $$$2 \cdot 10^3$$$ calculations, which will total $$$8 \cdot 10^7$$$ operations;
  • it will add $$$200$$$ integers to the data structure, which will total $$$4 \cdot 10^6$$$ integers and $$$2 \cdot 10^7$$$ additional operations.

Thus, the solution:

  • performs $$$8 \cdot 10^7 + 2 \cdot 10^7 = 10^8 \le 10^8$$$ — the time limit is not exceeded.
  • stores $$$4 \cdot 10^6 \le 2 \cdot 10^7$$$ integers — the memory limit is not exceeded;

Accordingly, this solution will receive the verdict OK.

Second test example

Aidar wrote the solution to the problem in C++.

In total, the solution will perform $$$10^5$$$ iterations, on each of which:

  • it will perform $$$0$$$ additional calculations;
  • it will add $$$300$$$ integers to the data structure, which will total $$$3 \cdot 10^7$$$ integers and $$$15 \cdot 10^7$$$ operations.

Thus, the solution

  • performs $$$1.5 \cdot 10^8 \le 5 \cdot 10^8$$$ operations — the time limit is not exceeded.
  • stores $$$3 \cdot 10^7 \gt 2 \cdot 10^7$$$ integers — the memory limit is exceeded;

Accordingly, this solution will receive the verdict ML.

Third test example

Aidar wrote the solution to the problem in Python.

In total, the solution will perform $$$10^6$$$ iterations, on each of which:

  • it will perform $$$10^6$$$ calculations, which will total $$$2 \cdot 10^{12}$$$ operations;
  • it will add $$$0$$$ integers to the data structure, which will not add any additional operations.

Thus, the solution

  • performs $$$2 \cdot 10^{12} \gt 2 \cdot 10^7$$$ operations — the time limit is exceeded.
  • stores nothing — the memory limit is not exceeded;

Accordingly, this solution will receive the verdict TL.

Fourth test example

This test is completely analogous to the first test, except for the increased number of loop iterations.

In total, the solution will perform $$$2 \cdot 10^6$$$ iterations, on each of which:

  • it will perform $$$2 \cdot 10^3$$$ calculations, which will total $$$8 \cdot 10^9$$$ operations;
  • it will add $$$200$$$ integers to the data structure, which will total $$$4 \cdot 10^8$$$ integers and $$$2 \cdot 10^9$$$ additional operations.

Thus, the solution:

  • performs $$$8 \cdot 10^9 + 2 \cdot 10^9 = 10^{10} \gt 10^8$$$ — the time limit is exceeded.
  • stores $$$4 \cdot 10^8 \gt 2 \cdot 10^7$$$ integers — the memory limit is exceeded;

Accordingly, this solution may receive any of the verdicts — it is necessary to output TL and ML.