SOLVE

LATER

Making chocolate cakes

/

Lihas is a foodie. His love for food is never ending, nor is his love for chocolates. Today, his mother decides to make chocolate cake for him.

There are **M** ingredients needed for the cake and there are **N** containers for each ingredient, i.e. container **C _{m,n}** contains the amount of ingredient

Also, each container has a capacity **K _{m,n}** which denotes the maximum capacity which can come in a container. If more amount of that ingredient is added, the container will overflow and the extra capacity will flow out. Also, you need to make sure that the amount of ingredient in any container does not go below zero.

Now Lihas's mother uses contiguous containers of each type. For instance, to make the cake, if she uses the segment of containers from index **L** to **R**, then the total cake she can make for Lihas is:

**CAKE = min _{i=1..M} (sum_{j=L..R} (C_{i,j}))**

That is, the amount of cake made if Lihas's mother uses the segment of containers from L to R is the minimum of (sum of amount of ingredient from container L to R) for each container.

There are 2 types of queries:

**Type 1**: In the first type of query, there are three numbers **X**, **Y** and **Z**. In this type of query, you add **Z** to the container **C _{x,y}**. Keep in mind the capacity of this container should neither go below zero nor above it's limit

**Type 2**: In this query, you will be given two indices **L** and **R**, and you need to find the amount of cake Lihas's mother can make using all ingredients in containers from index **L** to **R** inclusive, 1 based indexing.

**INPUT**

The first line of input will contain 3 integers **M**, **N** and **Q**, the number of ingredients, the number of containers for each ingredient, and the number of queries.

The next **M** lines contains in each line **N** integers, the capacities of container **n** of ingredient **m**, i.e. **K _{m, n}**.

The next **M** lines contains in each line **N** integers, the initial capacities of container **n** of ingredient **m**, i.e. **V _{m, n}**.

The next **Q** lines contain an integer **1** or **2**, the type of query.

If the query is of type **1**, you will get 3 integers **X**, **Y** and **Z**.

If the query is of type **2**. you will get 2 integers **L** and **R**

1 <= M <= 10

1 <= N <= 100000

1 <= Q <= 100000

1 <= K_{m, n} <= 1000000

1 <= V_{m, n} <= K_{m, n}

1 <= X <= M

1 <= Y <= N

-1000000 <= Z <= 1000000

1 <= L <= R <= N

**OUTPUT**

For each query of type **2**, you need to print the amount of cake Lihas's mother can make for him.

**SCORING**

Scoring will be as follows:

`Score = (1 - c / 2500) * 250`

,
where `c`

is the number of characters in your code. In case the characters exceed 2500, your score will be zero.

3 4 8 50 50 50 50 50 50 50 50 50 50 50 50 48 10 13 34 17 15 14 50 50 4 28 13 1 2 2 45 2 1 4 1 1 1 -15 2 1 4 1 3 4 40 2 1 4 1 1 2 40 2 1 4

Explanation

You are given 3 ingredients, with 4 containers for each ingredient, with each container for each of the ingredient having limit of 50.

In the first query, the amount of second ingredient in the second container increases by 45. But since new value is greater than the limit, i.e. 50, extra overflows and the amount in the container is 50.

The quantity of ingredients in the containers after the update are (space separated 1-indexed):

**Ingredient 1:** 48 10 13 34

**Ingredient 2:** 17 50 14 50

**Ingredient 3:** 50 4 28 13

The second query asks for the cake Lihas's mother can make with all ingredients from index 1 to 4, i.e using all the containers for each ingredient. The total sum of ingredients from index 1 to 4 is:

**Ingredient 1:** 105

**Ingredient 2:** 131

**Ingredient 3:** 95

The minimum amount of ingredient is ingredient 3, which is **95** units. Therefore Lihas's mother can make **95** units of cake from all ingredients with container indices 1 to 4.

The third query reduces the quantity by **15** of ingredient 1 in container 1.

The fourth query is similar to the second query.

The fifth query adds **40** units of ingredient **3** to its corresponding container 4. But since the initial quantity was **13**, new quantity is **53** and capacity is **50**, some of it overflows for the final quantity to be **50**. The quantities in the containers now are:

**Ingredient 1:** 33 10 13 34

**Ingredient 2:** 17 50 14 50

**Ingredient 3:** 50 4 28 50

Time Limit:
2.535 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...