#include <stdio.h>
#define RIVER_LENGTH 10000
int main() {
int num_cases;
int cases[num_cases];
int N;
int s1[RIVER_LENGTH] = {1};
int s3[RIVER_LENGTH] = {3};
int s9[RIVER_LENGTH] = {9};
int i;
int temp;
for (i = 1; i < RIVER_LENGTH; i++) {
s1[i] = temp = s1[i-1];
while (temp) {
s1[i] += temp % 10;
temp /= 10;
}
}
for (i = 1; i < RIVER_LENGTH; i++) {
s3[i] = temp = s3[i-1];
while (temp) {
s3[i] += temp % 10;
temp /= 10;
}
}
for (i = 1; i < RIVER_LENGTH; i++) {
s9[i] = temp = s9[i-1];
while (temp) {
s9[i] += temp % 10;
temp /= 10;
}
}
int start;
int end;
int pivot;
for (i=1; i <= num_cases; i++) {
}
for (i=1; i <= num_cases; i++) {
N = cases[i];
while (1) {
temp = N;
while (temp) {
N += temp % 10;
temp /= 10;
}
start = 0;
end = RIVER_LENGTH;
pivot = 1;
while (end != start && pivot != RIVER_LENGTH - 1) {
pivot = start + ((end - start) >> 1);
if (s1[pivot] == N) {
printf("first meets river 1 at %d\n\n", N
); goto case_done;
} else if (N < s1[pivot]){
end = pivot;
} else {
start = pivot+1;
}
}
start = 0;
end = RIVER_LENGTH;
pivot = 1;
while (end != start && pivot != RIVER_LENGTH - 1) {
pivot = start + ((end - start) >> 1);
if (s3[pivot] == N) {
printf("first meets river 3 at %d\n\n", N
); goto case_done;
} else if (N < s3[pivot]){
end = pivot;
} else {
start = pivot+1;
}
}
start = 0;
end = RIVER_LENGTH;
pivot = 1;
while (end != start && pivot != RIVER_LENGTH - 1) {
pivot = start + ((end - start) >> 1);
if (s9[pivot] == N) {
printf("first meets river 9 at %d\n\n", N
); goto case_done;
} else if (N < s9[pivot]){
end = pivot;
} else {
start = pivot+1;
}
}
}
case_done:;
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIFJJVkVSX0xFTkdUSCAxMDAwMAoKaW50IG1haW4oKSB7CiAgICBpbnQgbnVtX2Nhc2VzOwogICAgc2NhbmYoIiVkIiwgJm51bV9jYXNlcyk7CiAgICBpbnQgY2FzZXNbbnVtX2Nhc2VzXTsKICAgIGludCBOOwogICAgaW50IHMxW1JJVkVSX0xFTkdUSF0gPSB7MX07CiAgICBpbnQgczNbUklWRVJfTEVOR1RIXSA9IHszfTsKICAgIGludCBzOVtSSVZFUl9MRU5HVEhdID0gezl9OwogICAgaW50IGk7CiAgICBpbnQgdGVtcDsKCiAgICBmb3IgKGkgPSAxOyBpIDwgUklWRVJfTEVOR1RIOyBpKyspIHsKICAgICAgICBzMVtpXSA9IHRlbXAgPSBzMVtpLTFdOwogICAgICAgIHdoaWxlICh0ZW1wKSB7CiAgICAgICAgICAgIHMxW2ldICs9IHRlbXAgJSAxMDsKICAgICAgICAgICAgdGVtcCAvPSAxMDsKICAgICAgICB9CiAgICB9CgogICAgZm9yIChpID0gMTsgaSA8IFJJVkVSX0xFTkdUSDsgaSsrKSB7CiAgICAgICAgczNbaV0gPSB0ZW1wID0gczNbaS0xXTsKICAgICAgICB3aGlsZSAodGVtcCkgewogICAgICAgICAgICBzM1tpXSArPSB0ZW1wICUgMTA7CiAgICAgICAgICAgIHRlbXAgLz0gMTA7CiAgICAgICAgfQogICAgfQoKICAgIGZvciAoaSA9IDE7IGkgPCBSSVZFUl9MRU5HVEg7IGkrKykgewogICAgICAgIHM5W2ldID0gdGVtcCA9IHM5W2ktMV07CiAgICAgICAgd2hpbGUgKHRlbXApIHsKICAgICAgICAgICAgczlbaV0gKz0gdGVtcCAlIDEwOwogICAgICAgICAgICB0ZW1wIC89IDEwOwogICAgICAgIH0KICAgIH0KCiAgICBpbnQgc3RhcnQ7CiAgICBpbnQgZW5kOwogICAgaW50IHBpdm90OwoKICAgIGZvciAoaT0xOyBpIDw9IG51bV9jYXNlczsgaSsrKSB7CiAgICAgICAgc2NhbmYoIiVkIiwgJmNhc2VzW2ldKTsKICAgIH0KCiAgICBmb3IgKGk9MTsgaSA8PSBudW1fY2FzZXM7IGkrKykgewogICAgICAgIHByaW50ZigiQ2FzZSAjJWRcblxuIiwgaSk7CiAgICAgICAgTiA9IGNhc2VzW2ldOwoKICAgICAgICB3aGlsZSAoMSkgewoKICAgICAgICAgICAgdGVtcCA9IE47CiAgICAgICAgICAgIHdoaWxlICh0ZW1wKSB7CiAgICAgICAgICAgICAgICBOICs9IHRlbXAgJSAxMDsKICAgICAgICAgICAgICAgIHRlbXAgLz0gMTA7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIHN0YXJ0ID0gMDsKICAgICAgICAgICAgZW5kID0gUklWRVJfTEVOR1RIOwogICAgICAgICAgICBwaXZvdCA9IDE7CgogICAgICAgICAgICB3aGlsZSAoZW5kICE9IHN0YXJ0ICYmIHBpdm90ICE9IFJJVkVSX0xFTkdUSCAtIDEpIHsKICAgICAgICAgICAgICAgIHBpdm90ID0gc3RhcnQgKyAoKGVuZCAtIHN0YXJ0KSA+PiAxKTsKICAgICAgICAgICAgICAgIGlmIChzMVtwaXZvdF0gPT0gTikgewogICAgICAgICAgICAgICAgICAgIHByaW50ZigiZmlyc3QgbWVldHMgcml2ZXIgMSBhdCAlZFxuXG4iLCBOKTsKICAgICAgICAgICAgICAgICAgICBnb3RvIGNhc2VfZG9uZTsKICAgICAgICAgICAgICAgIH0gZWxzZSBpZiAoTiA8IHMxW3Bpdm90XSl7CiAgICAgICAgICAgICAgICAgICAgZW5kID0gcGl2b3Q7CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIHN0YXJ0ID0gcGl2b3QrMTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQoKICAgICAgICAgICAgc3RhcnQgPSAwOwogICAgICAgICAgICBlbmQgPSBSSVZFUl9MRU5HVEg7CiAgICAgICAgICAgIHBpdm90ID0gMTsKCiAgICAgICAgICAgIHdoaWxlIChlbmQgIT0gc3RhcnQgJiYgcGl2b3QgIT0gUklWRVJfTEVOR1RIIC0gMSkgewogICAgICAgICAgICAgICAgcGl2b3QgPSBzdGFydCArICgoZW5kIC0gc3RhcnQpID4+IDEpOwogICAgICAgICAgICAgICAgaWYgKHMzW3Bpdm90XSA9PSBOKSB7CiAgICAgICAgICAgICAgICAgICAgcHJpbnRmKCJmaXJzdCBtZWV0cyByaXZlciAzIGF0ICVkXG5cbiIsIE4pOwogICAgICAgICAgICAgICAgICAgIGdvdG8gY2FzZV9kb25lOwogICAgICAgICAgICAgICAgfSBlbHNlIGlmIChOIDwgczNbcGl2b3RdKXsKICAgICAgICAgICAgICAgICAgICBlbmQgPSBwaXZvdDsKICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgc3RhcnQgPSBwaXZvdCsxOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CgogICAgICAgICAgICBzdGFydCA9IDA7CiAgICAgICAgICAgIGVuZCA9IFJJVkVSX0xFTkdUSDsKICAgICAgICAgICAgcGl2b3QgPSAxOwoKICAgICAgICAgICAgd2hpbGUgKGVuZCAhPSBzdGFydCAmJiBwaXZvdCAhPSBSSVZFUl9MRU5HVEggLSAxKSB7CiAgICAgICAgICAgICAgICBwaXZvdCA9IHN0YXJ0ICsgKChlbmQgLSBzdGFydCkgPj4gMSk7CiAgICAgICAgICAgICAgICBpZiAoczlbcGl2b3RdID09IE4pIHsKICAgICAgICAgICAgICAgICAgICBwcmludGYoImZpcnN0IG1lZXRzIHJpdmVyIDkgYXQgJWRcblxuIiwgTik7CiAgICAgICAgICAgICAgICAgICAgZ290byBjYXNlX2RvbmU7CiAgICAgICAgICAgICAgICB9IGVsc2UgaWYgKE4gPCBzOVtwaXZvdF0pewogICAgICAgICAgICAgICAgICAgIGVuZCA9IHBpdm90OwogICAgICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgICAgICBzdGFydCA9IHBpdm90KzE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGNhc2VfZG9uZTo7CgogICAgfQp9