long long floor_sum( long long n, long long m, long long a, long long b) {
long long ans = 0 ;
if ( a >= m) {
ans + = ( n - 1 ) * n * ( a / m) / 2 ;
a % = m;
}
if ( b >= m) {
ans + = n * ( b / m) ;
b % = m;
}
long long y_max = ( a * n + b) / m, x_max = ( y_max * m - b) ;
if ( y_max == 0 ) return ans;
ans + = ( n - ( x_max + a - 1 ) / a) * y_max;
ans + = floor_sum( y_max, a, m, ( a - x_max % a) % a) ;
return ans;
}
bG9uZyBsb25nIGZsb29yX3N1bShsb25nIGxvbmcgbiwgbG9uZyBsb25nIG0sIGxvbmcgbG9uZyBhLCBsb25nIGxvbmcgYikgewogIGxvbmcgbG9uZyBhbnMgPSAwOwogIGlmIChhID49IG0pIHsKICAgICAgYW5zICs9IChuIC0gMSkgKiBuICogKGEgLyBtKSAvIDI7CiAgICAgIGEgJT0gbTsKICB9CiAgaWYgKGIgPj0gbSkgewogICAgICBhbnMgKz0gbiAqIChiIC8gbSk7CiAgICAgIGIgJT0gbTsKICB9CiAKICBsb25nIGxvbmcgeV9tYXggPSAoYSAqIG4gKyBiKSAvIG0sIHhfbWF4ID0gKHlfbWF4ICogbSAtIGIpOwogIGlmICh5X21heCA9PSAwKSByZXR1cm4gYW5zOwogIGFucyArPSAobiAtICh4X21heCArIGEgLSAxKSAvIGEpICogeV9tYXg7CiAgYW5zICs9IGZsb29yX3N1bSh5X21heCwgYSwgbSwgKGEgLSB4X21heCAlIGEpICUgYSk7CiAgcmV0dXJuIGFuczsKfSA=