Hello, Can anyone provide hint to solve below problem on segment tree.

Problem Link:Problem Link

Problem Description:

A city is a sequence of n cells numbered from 0 to n−1. Initially, all cells are empty. Then m events of one of two types occur sequentially:

a building with the strength h is being constructed in the cell i (if the building already existed in this cell, it is demolished and replaced with a new one),

in the interval from l to r−1 an earthquake of power p happens, it destroys all buildings whose strength is not more than p. Your task is for each earthquake to say how many buildings it will destroy.

Input

The first line contains the numbers n and m, the number of cells and the number of events (1≤n,m≤105). The following m lines describe events. The description of each event is as follows:

1 i h: a building with the strength h is constructed in the cell i (0≤i<n, 1≤h≤10^9).

2 l r p: an earthquake of power p happens on a segment from l to r−1 (0≤l<r≤n, 0≤p≤10^9).

Output

For each event of the second type, print how many buildings were destroyed.