Problem E
Free Real Estate

Tim Heidecker has decided to act as a real estate agent for a day. Due to his lack of qualifications, only one real estate agency would hire him; Array-like Penthouse Solutions (APS).

Tim has been tasked to sell penthouses on Sequence Road, where all apartments are adjacent and on one continuous line. The penthouses are all brand new and were built to look identical. For this reason, all penthouses are initially set at the same price. However, time is not equally kind to all penthouses, and therefore prices of individual penthouses may change over time. Tim has made an agreement with APS that they will text him whenever there is an update on the price of a penthouse, and his contract states that he may only sell penthouses for the exact current price.

Tim has noticed that sometimes, APS accidentally updates the price of a penthouse to a negative price, and he would really like a new penthouse apartment, as his old duplex is dilapidated. He tried to purchase one of the penthouses with a negative price, but was rejected. However, he was able to make a purchase when the price was 0…

APS brands itself with selling many adjacent penthouses in a single transaction for its rich audience, as they can be joined into a single larger penthouse later. With this information, Tim has concocted a plan: If he happens to stumble across a sequence of one or more penthouses that have price exactly 0, he will buy it for himself. However, Tim is lazy and does not want to check the price of all groups of penthouses on his own. Instead, whenever a client asks for the price of (several adjacent) penthouses, he will check if the house is free (the price is exactly 0). If it is free, he will tell the client that the apartments were just purchased (and then purchase them himself when he gets off of work).

Your task is to help Tim in the following way:

• You must support updating prices for each penthouse separately.

• You must be able to give the price of a single, or of a group of adjacent, penthouse(s).

  • If the price for the given query is exactly 0, you must notify him of this so he does not sell it to the client.

  • Tim doesn’t care if the price is positive or negative, so if a price is negative, just relay the price either way; that’s the client’s problem.

Input

The first line of input contains three space-separated integers $L$, $N$ and $P$, where $L$ is the length of the array, $N$ is the number of operations and $1 \leq P \leq 100,000$ is the initial price of all penthouses. The ranges of $L$ and $N$ vary depending on the test group. Operations are either updates or queries, and the first penthouse has index 1. Following the first line of input are $N$ operations, each on their own line:

• Updates are in the form ‘update i v‘, where $i, v$ are both integers; $1 \leq i \leq L$ is the index of the penthouse whose value should be updated to the new price $-100,000 \leq v \leq 100,000$.

• Queries are in the form ‘query s e‘, where $1 \leq s \leq e \leq L$ are both integers; $s$ is the index for the start of the sub-array and $e$ is the end of it (both inclusive).

Output

For each query operation, output a line with a single integer; the sum of the subarray from $s$ to $e$. If the sum is $0$, output the string ‘it’s free real estate‘ instead.

Scoring

There are four test groups, each giving 25 points. The maximum is 100 points:

• Group 1: $1 \leq L \leq 10,000$ and $1 \leq N \leq 10,000$.

• Group 2: $1 \leq L \leq 100,000$ and $1 \leq N \leq 100,000$. In addition, all updates are given before the first query.

• Group 3: $1 \leq L \leq 100,000$ and $1 \leq N \leq 100,000$.

• Group 4: $1 \leq L \leq 1,000,000$ and $1 \leq N \leq 1,000,000$.

4 7 50
query 1 4
update 1 20
update 2 -100
update 3 100
query 2 3
update 4 -4
query 4 4

200
it's free real estate
-4

4 6 2
update 4 4
update 1 1
update 3 3
query 2 4
update 4 2
query 3 4

9
5

14 4 10
query 13 14
query 12 14
query 6 14
query 9 12

20
30
90
40

10 10 40491
update 5 986
update 8 -174
update 2 -345
update 4 -898
update 7 -353
query 4 7
query 8 9
query 2 4
query 1 9
query 6 9

40226
40317
39248
161180
80455