write a go solution for D2. Removal of a Sequence (Hard Version)time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis is the hard version of the problem. The difference between the versions is the constraint on x; in this version, x<=10^12.Polycarp has a sequence of all natural numbers from 1 to 10^12. He decides to modify this sequence by performing the following action x times:  Simultaneously remove all numbers at positions y, 2*y, 3*y, ..., m*y<=n, where n is the length of the current sequence. After that, Polycarp wants to find the k-th number in the remaining sequence or determine that the length of the resulting sequence is less than k. Help Polycarp solve this problem!Consider an example. Let x=2, y=3, k=5, then:  The numbers crossed out with a red line were removed after the first operation, and the numbers crossed out with a blue line were removed after the second operation. Thus, the number at position k=5 is the number 10.InputEach test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10). The description of the test cases follows. The only line of each test case contains three integers x, y, k (1<=x,y,k<=10^12).OutputFor each test case, output a positive integer that is at the k-th position in the resulting sequence, or -1 if the length of the resulting sequence is less than k.ExampleInput62 3 52 5 120 2 1000000000000175 10 281000000000 998244353 19999999991 1 1Output101-123390303044672518823-1. Output only the code with no comments, explanation, or additional text.