/* ref.c -- Lamping & Veach (2014), the reference form: 64-bit wrapping
 * multiply, and the jump computed with a double, exactly as published in
 * "A Fast, Minimal Memory, Consistent Hash Algorithm", figure 5.
 *
 * This file exists so the Python module's docstring claim ("results match the
 * C reference") can be graded against an implementation the Python module did
 * not write, rather than against itself.  Nothing here mirrors the Python
 * control flow: the loop, the multiply and the double division are the
 * paper's, and the key comes from stdin, not from a hash fold.
 *
 * stdin:  one "<u64> <n>" pair per line, n <= 2^31-1
 * stdout: "<u64> <n> <bucket>"
 */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

static int32_t jump_ref(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (int64_t)((double)(b + 1) * (double)(1LL << 31) /
                      (double)((key >> 33) + 1));
    }
    return (int32_t)b;
}

int main(void) {
    unsigned long long k;
    long n;
    while (scanf("%llu %ld", &k, &n) == 2) {
        if (n < 1 || n > 2147483647L) {
            fprintf(stderr, "ref: n out of range: %ld\n", n);
            return 2;
        }
        printf("%llu %ld %d\n", k, n, jump_ref((uint64_t)k, (int32_t)n));
    }
    return 0;
}