My AC is 0.8 seconds, what is the idea for 0.01sec solutions?

may be precalc?

Yea, precalc actually does work. I had an ineffecient solution which spent ~30 seconds and ~65 MB, so then i tried to precalc, but my initial variant didn't pass because it was 204kb of code, and the limit of 64kb is suddenly back (i don't recall it from before...)
In the end, i finally managed to compress it down to 63kb, due to the fact that out of 100k values, certain four numbers were present in 80%+ cases.

java  0.156 | 45 000 КБ

precalc)

100000 char's to 64K

theare is some big number ang long path from it to [1,100] by dividing
we can start moving from any place of this path