도시에 N명의 사람들이 살고 있다. 이 중 일부는 참말쟁이이고, 나머지는 거짓말쟁이이다.

더욱 구체적으로, 참말쟁이들은 항상 옳은 말만을 하지만, 거짓말쟁이들은 옳은 말이든 거짓말이든 아무 말이나 한다.

모든 사람들에게, 참말쟁이들이 이 도시에 몇 명이 존재하는지 물었다.

그 결과, i번째 사람은 참말쟁이가 A_i명 이상 B_i명 이하라고 대답하였다.

당신이 할 일은 이 증언들을 바탕으로 가능한 참말쟁이의 최대 명수를 구하는 것이다.

그런데, 문제가 발생했다. 사람들의 기억력이 그리 좋지는 못하다는 것이다.

Q번 증언이 바뀌며, i번째 증언 바뀜에서는 P_i번 사람의 증언이 "참말쟁이가 L_i명 이상, R_i명 이하이다." 로 바뀐다.

초기 상태를 포함해서 Q+1번의 상황에 대해 각각 참말쟁이의 최대 명수를 구하여라.

Truth Tellers timer 6s memory 2048MB

Truth Tellers 6s 2048MB