Ivan and Isabel are iguanas who live in the Iguana Islands. The archipelago consists of $$$N$$$ islands ($$$1 \leq N \leq 2*10^5$$$), indexed from $$$1..N$$$ and arranged in line in the order of their indices, each of which consists of a single type of fruit denoted as $$$f_i$$$. The amount of fruit on island $$$i$$$ is denoted as $$$q_i$$$. ($$$1 \leq f_i, q_i \leq 10^9$$$). The fruits on these islands are special, and can only be eaten in quantities of $$${f_i}^k$$$, where k is a non-negative integer ($$$0 \leq k$$$). During each of the next Q days ($$$1 \leq Q \leq 2*10^5$$$), the following will happen:

• At the start of the day, all fruit on all islands will be replenished back to its original state (the fruit on these islands grows very fast at night).
• A storm approaches all islands with an index less than $$$l_i$$$ or greater than $$$r_i$$$, so Ivan and Isabel will not visit those islands during the $$$i$$$th day.
• Ivan and Isabel take turns eating from an island where it is not raining, beginning with Ivan. If they choose to eat from island $$$i$$$, then they must eat $$${f_i}^k$$$ fruit from island $$$i$$$, for some non-negative integer $$$k$$$.
• The last iguana to eat food before all of the available islands are empty will be well-fed, while the other iguana will starve for the rest of the day.

For each of the $$$Q$$$ days, determine which iguana will be well-fed, assuming the iguanas are very intelligent, and will always make the decision which minimizes their chance of starving at the end of the day.