h=a$h=a$가 되는 최초의 시각을 p$p$, 그 다음으로 h=a$h=a$가 되는 최초의 시각을 q$q$라고 합시다. 그러면 시각 t$t$에 h=a$h=a$라는 것과 적당한 음이 아닌 정수 s$s$에 대하여 t=p+s(q-p)$t=p+s(q-p)$라는 것이 동치임을 알 수 있습니다.
따라서 h_1,a_1$h_1,a_1$에 대한 p_1,q_1$p_1,q_1$과 h_2,a_2$h_2,a_2$에 대한 p_2,q_2$p_2,q_2$를 구한 뒤, 음이 아닌 정수 s_1,s_2$s_1,s_2$에 대하여 t=p_1+s_1(q_1-p_1)=p_2+s_2(q_2-p_2)$t=p_1+s_1(q_1-p_1)=p_2+s_2(q_2-p_2)$를 만족하는 최소의 t$t$가 답이 됩니다. p_1,q_1,p_2,q_2$p_1,q_1,p_2,q_2$는 최대 2m$2m$이고, 최소의 t$t$는 연립합동식을 해결함으로써 구할 수 있습니다. 총 시간복잡도는 O(m)$O(m)$이 됩니다. 몇 가지 예외(q$q$가 존재하지 않는 등)에 대해서는 따로 처리를 해 주어야 합니다.
이 문제에서 답이 32-bit integer를 넘어갈 수 있기 때문에 64-bit integer 등을 사용해야 합니다.

문제에서는 크기가 x$x$인 그룹들 중 대해 최대 strength를 묻고 있지만, 저는 반대로 strength가 a_i$a_i$ 이상인 가장 큰 그룹을 찾는 식으로 접근했습니다.
a_i$a_i$가 큰 순서대로 보면서, 현재까지 나온 수들로 이루어진 그룹들 중 i$i$를 포함하는 가장 큰 그룹을 찾습니다. 이를 위해서 Union-Find 자료구조를 사용했습니다. 만약 i-1$i-1$이 이전에 나온 수라면 i-1$i-1$과 i$i$를 합치고, i+1$i+1$이 이전에 나온 수라면 i+1$i+1$과 i$i$를 합칩니다. 이를 수행한 뒤 i$i$가 포함된 Union의 크기가 곧 i$i$를 포함하는 가장 큰 그룹의 크기입니다. Union의 크기와 a_i$a_i$를 기록한 뒤, 마지막에 정리하여 출력해주면 됩니다. 총 시간복잡도는 O(n \log n)$O(n \log n)$이 됩니다.

포함-배제의 원리와 a_i$a_i$의 소인수가 최대 6개라는 점을 이용해서 풀었습니다.
먼저 1$1$ 이상 500,000$500,000$ 이하의 모든 수에 대하여 소인수의 개수가 짝수인지 홀수인지를 판별합니다. 이는 에라토스테네스의 체를 변형하여 빠른 시간 안에 구할 수 있습니다. 쿼리가 들어올 때마다 포함-배제의 원리를 이용하여 답을 구할 수 있습니다. 예를 들어 새로 추가되는 수가 10이라고 하면, 이는 소인수가 2와 5 두 개임을 알 수 있습니다. 그러면 서로소인 쌍의 개수는 예전에 추가된 수 중 (1의 배수의 개수)-(2의 배수의 개수)-(5의 배수의 개수)+(10의 배수의 개수)만큼 증가합니다. 이를 배열을 만들어 세고, a_i$a_i$의 소인수가 최대 6개이므로 2^6=64번의 참조로 쿼리의 답을 구할 수 있습니다.

x좌표가 같은 점들에 대해서 간선을 잇지 않은 두 점끼리 간선을 가능한 한 많이 이어줍니다. 예를 들어 x좌표가 3인 점들의 y좌표가 2, 5, 6, 8, 9라면 2와 5, 6과 8 간에 간선을 이어줍니다. (2와 8, 6과 9를 이어도 상관없습니다) y좌표가 같은 점들에 대해서도 똑같은 작업을 해 줍니다. 이렇게 만들어진 그래프는 이분그래프임을 알 수 있습니다.
여기서, 아직 방문하지 않은 임의의 점을 잡고 DFS를 합니다. 깊이가 홀수이면 붉은색을, 짝수이면 푸른색을 칠합니다. 이를 모든 점을 다 방문할 때까지 반복합니다. 이분그래프이므로 이렇게 색을 칠했을 때 인접한 두 정점 간에는 색이 다르다는 것을 알 수 있습니다. 또한 x좌표 또는 y좌표가 같은 점들 간에 간선을 가능한 한 많이 이었기 때문에 붉은색 점과 푸른색 점의 개수 차이가 많아야 1임을 알 수 있습니다. 총 시간복잡도는 O(n)$O(n)$입니다.