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.
  

The first line contains the numbers $n,m$, the number of cells and the number of events $(1≤n,m≤10^5)$. 
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)$.

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