Series Sum II

Problem Statement

You are given three integers $n$, $x$ and $k$.

You have the following infinite sequence $S = [1 \small\text{ mod } \normalsize k,\ \ \ (1 + 2) \small\text{ mod }\normalsize k,\ \ \ (1 + 2 + 3) \small\text{ mod }\normalsize k,\ ... ]$, in other words $S_i = (\sum_{j=1}^ij) \small\text{ mod }\normalsize k$.

Determine at which index (one-indexed) the $n^{th}$ occurrence of $x$ is in the sequence $S$ if $x$ occurs at least $n$ times, otherwise output $-1$.

Input Format

Your first line will contain three space-separated integers $n$, $x$ and $k$ respectively.

Output Format

You should output a single integer, representing the index (one-indexed) in $S$ at which the $n^{th}$ occurrence of $x$ appears. If it does not appear at least $n$ times, then output $-1$.

Constraints

• $1 \leq n \leq 10^{9}$
• $1 \leq k \leq 10^2$
• $0 \leq x \lt k$

Sample Cases

1 1 10

1

2 1 10

6

20 2 13

124

20 2 10

-1

Template

n, x, k = map(int, input().split())

# print your output