Hello! Could you please explain to me why my 94709653 gets WA4 in 1422F - Boring Queries? In my solution, I just use a segment tree to calculate lcm on the segment of the array. To calculate lcm of numbers a and b I use following fact: lcm(a, b) = a * b / gcd(a, b). Also, I take into account that we calculate lcm by modulo MOD. So lcm(a, b) = (((a * b) % MOD) * solve(gcd(a, b), MOD)) % MOD, where solve(x, m) returns such y that x * y ≡ 1 (mod m). Why it gets WA4? I think the idea is correct and I used verified patterns of segtree and functions loke gcd, lcm and solve (finding an inverse element in the residue ring modulo). Please help!!!

P.S. sorry for my poor English, I tried to use Grammarly and translator