This is the hard version of the problem. The difference is the constraint of n and m.
N gamblers (numbered from 1 to n) circle the round table clockwise. There is a large electronic screen and a large amount of money on the round table. They want to play a game. Before the game starts, the electronic screen will randomly display a positive integer M. they will start counting clockwise from  1, and the person who reports the number m will exit, and then the first person behind him will continue counting from 1, Repeat this until only one left. Then he will win all the money. But this person is a hacker. He has set the number to be displayed on the electronic screen in advance to ensure that he is the winner of the game. Your task is to find the hacker's number.

The first line  contains two integers n,m (1≤n,m≤2000000).

Print the hacker's number.

11 3

7