Let \(m_i := g_i + r_i\). We call a tuple \((m_1, x_1, m_2, x_2, m_3, x_3)\) nice if there exists an integer \(x\) that satisfies \(x \equiv x_i \pmod {m_i}\) for each \(i\). Our task is to compute the number of tuples \((i, j, k)\) that satisfies:

• \(0 \leq i < g_1\), \(0 \leq j < g_2\), \(0 \leq k < g_3\)
• \((m_1, i, m_2, j, m_3, k)\) is nice

First, let’s try to solve some easy cases. For example, if \(m_1, m_2, m_3\) are three distinct primes, the task is easy because all tuples with the modulos are nice.

Suppose that for some prime \(p\), \(p\) divides \(m_1\) but not \(m_2\) and \(m_3\). Notice the following fact:

• \((m_1, i, m_2, j, m_3, k)\) is nice iff \((m_1', i \% m_1', m_2, j, m_3, k)\) is nice, where \(m_1' = m_1 / p\).

Thus, we can “simplify” the modulos from \((m_1, m_2, m_3)\) to \((m_1', m_2, m_3)\).

A similar observation can be made when for some prime \(p\), \(ord_p m_1 >\max \{ ord_p m_2, ord_p m_3 \}\) holds:

• \((m_1, i, m_2, j, m_3, k)\) is nice iff \((m_1', i \% m_1', m_2, j, m_3, k)\) is nice, where \(m_1' = m_1 / p^t\), where t = \(ord_p m_1 -\max \{ ord_p m_2, ord_p m_3 \}\).

By repeating this simplification, we can assume the following conditions for the modulos:

• \(m_1\) divides \(LCM(m_2, m_3)\).
• \(m_2\) divides \(LCM(m_1, m_3)\).
• \(m_3\) divides \(LCM(m_1, m_2)\).

Now, we can prove that we can write \(m_1 = gab, m_2 = gac, m_3 = gbc\) for some integers \(g, a, b, c\). Without loss of generality, we can assume that \(a \leq b \leq c\).

Now a brute force works! Let’s simulate all changes of the two lights \(2, 3\) until time \(gabc = LCM(m_1, m_2, m_3)\). Until then, the two lights change their colors \(O(a + b)\) times. We can actually generate all changes because \(bc \leq gbc = m_3 \leq MAX = 10^{12}\), \(a \leq b \leq \sqrt{bc}\), and both \(a\) and \(b\) are \(O(\sqrt{MAX})\).