Under construction

Still being built. Things may change

Grid and Queries

Time limit2sMemory limit1024 MB

Summary
Starting from an N by N grid of zeros, the task applies queries that set a whole row or column to a value and prints the sum of a given row or column.
Level

Medium6 of 10

Topics
Segment tree, Implementation
Solved
No attempts yet

Problem

An N×NN \times N grid is given. Each cell holds one number, and initially every cell contains 00. Process the following queries.

  • 1 i v: Change every number in row ii to vv. (1≤i≤N,1≤v≤109)(1 \le i \le N, 1 \le v \le 10^9)
  • 2 i v: Change every number in column ii to vv. (1≤i≤N,1≤v≤109)(1 \le i \le N, 1 \le v \le 10^9)
  • 3 i: Print the sum of all numbers in row ii. (1≤i≤N)(1 \le i \le N)
  • 4 i: Print the sum of all numbers in column ii. (1≤i≤N)(1 \le i \le N)

It is guaranteed that there is at least one 3 i or 4 i query.

Input

The first line contains the grid size NN and the number of queries QQ.

Each of the next QQ lines contains one query.

Output

For each 3 i and 4 i query, print the sum of the corresponding row or column on its own line, in the order the queries are given.

Constraints

  • 1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5

Examples1

  1. Example 1

    Input
    5 7
1 2 5
2 3 10
3 2
4 3
1 1 3
2 5 7
4 5
    Expected output
    30
50
35