{"raw_statement":[{"iden":"statement","content":"You are given a sequence of signed 64-bit integers defined as follows: \n\nLet's call a sequence element xp _repeatable_ if it occurs later in the sequence — meaning that there exists such q, q > p, that xq = xp. The _first repeatable_ element M of the sequence is such an element xm that xm is _repeatable_, and none of the xp where p < m are _repeatable_.\n\nGiven A, B and C, your task is to find the index of the second occurrence of the _first repeatable_ element M in the sequence if the index is less or equal to 2·107. Per definition, the first element of the sequence has index 0.\n\nThe only line of input contains three signed 64-bit integers: A, B and C (B > 0, C > 0).\n\nPrint a single integer  — the index of the second occurence of the _first repeatable_ member if it is less or equal to 2·107. Print  - 1 if the index is more than 2·107.\n\nIn the first sample test the sequence starts with the following numbers: 1, 3, 7, 6, 3, 7. The _first repeatable_ element is 3. The second occurence of 3 has index 4. \n\nIn the second sample test the sequence starts with the following numbers: 1, 2305843009213693951, -4611686018427387903, 6917529027641081855, 0, 0, 0. The _first repeatable_ element is 0. The second occurence of 0 has index 5. \n\nIn the third sample test the sequence starts with the following numbers: 1, -2, 4, -3, 1, -2, 4. The _first repeatable_ element is 1. The second occurence of 1 has index 4.\n\n"},{"iden":"input","content":"The only line of input contains three signed 64-bit integers: A, B and C (B > 0, C > 0)."},{"iden":"output","content":"Print a single integer  — the index of the second occurence of the _first repeatable_ member if it is less or equal to 2·107. Print  - 1 if the index is more than 2·107."},{"iden":"examples","content":"Input2 2 9Output4Input2305843009213693951 1 9223372036854775807Output5Input-2 1 5Output4"},{"iden":"note","content":"In the first sample test the sequence starts with the following numbers: 1, 3, 7, 6, 3, 7. The _first repeatable_ element is 3. The second occurence of 3 has index 4. In the second sample test the sequence starts with the following numbers: 1, 2305843009213693951, -4611686018427387903, 6917529027641081855, 0, 0, 0. The _first repeatable_ element is 0. The second occurence of 0 has index 5. In the third sample test the sequence starts with the following numbers: 1, -2, 4, -3, 1, -2, 4. The _first repeatable_ element is 1. The second occurence of 1 has index 4."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ A, B, C \\in \\mathbb{Z} $ with $ B > 0 $, $ C > 0 $.  \nDefine the sequence $ (x_i)_{i=0}^{\\infty} $ by:  \n$$\nx_0 = A, \\quad x_{i} = (x_{i-1} \\cdot B + C) \\mod 2^{64} \\quad \\text{for } i \\geq 1.\n$$\n\nAn element $ x_p $ is *repeatable* if $ \\exists q > p $ such that $ x_q = x_p $.  \nThe *first repeatable* element $ M $ is $ x_m $, where $ m $ is the smallest index such that $ x_m $ is repeatable.\n\nLet $ j $ be the index of the *second occurrence* of $ M $, i.e., the smallest $ j > m $ such that $ x_j = x_m $.\n\n**Constraints**  \n- $ B > 0 $, $ C > 0 $  \n- All values are signed 64-bit integers (modulo $ 2^{64} $ arithmetic)  \n- We only consider $ j \\leq 2 \\cdot 10^7 $\n\n**Objective**  \nCompute $ j $ if $ j \\leq 2 \\cdot 10^7 $; otherwise output $ -1 $.","simple_statement":"Given A, B, C, generate a sequence where x[0] = A, and x[i] = (x[i-1] * B + C) mod 2^64.  \nFind the index of the second occurrence of the first number that appears twice in the sequence.  \nIf that index > 2·10^7, print -1.","has_page_source":false}