Where does the loop start?

Problem

A chain of jobs may loop back: the last node's next can point to an earlier node. Given the values and the position that the last node points back to (-1 means no loop), print the value stored in the first node of the loop, or NONE if there is no loop. Values can repeat, so find the node, not the value.

Input, output and limits

Input: Line 1: the values. Line 2: an integer pos, either -1 or a position from 0 to length - 1.
Output: The value at the first node of the loop, or NONE.
Constraints: 1 ≤ number of values ≤ 10000
1 ≤ each value ≤ 1000000000
-1 ≤ pos < number of values

Examples

Example 1

Input

3 2 0 4
1

Output

Example 2

Input

1 2
-1

Output

NONE

Hints

Try the problem first. Open one hint at a time.

Hint 1

First find a meeting point with slow and fast pointers.

Hint 2

Then restart one pointer at the head and move both one step at a time.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Linked Lists problems

Problem

Input, output and limits

Examples

Hints

More Linked Lists problems