#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>
#define infile "bile4.in"
#define outfile "bile4.out"
using namespace std;
const int inf = (int)((1LL << 31) - 1);
class InputReader {
public:
InputReader() {}
InputReader(const char *file_name) {
input_file = fopen(file_name, "r");
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
inline InputReader &operator >>(int &n) {
while (buffer[cursor] < '0' || buffer[cursor] > '9') {
advance();
}
n = 0;
while ('0' <= buffer[cursor] && buffer[cursor] <= '9') {
n = n * 10 + buffer[cursor] - '0';
advance();
}
return *this;
}
private:
FILE *input_file;
static const int SIZE = 1 << 17;
int cursor;
char buffer[SIZE];
inline void advance() {
++cursor;
if (cursor == SIZE) {
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
}
};
class Treap {
private:
struct Node {
int key, freq, priority, size;
Node *left, *right;
Node() {
size = 0;
}
Node(int key, int freq, int priority, int size, Node *left, Node *right) {
this->key = key;
this->freq = freq;
this->priority = priority;
this->size = size;
this->left = left;
this->right = right;
}
} *root, *_empty;
void updateSize(Node* &node) {
node->size = node->freq + node->left->size + node->right->size;
}
void rotLeft(Node* &node) {
Node *temp = node->left;
node->left = temp->right;
temp->right = node;
node = temp;
updateSize(node->right);
updateSize(node);
}
void rotRight(Node* &node) {
Node *temp = node->right;
node->right = temp->left;
temp->left = node;
node = temp;
updateSize(node->left);
updateSize(node);
}
void balance(Node* &node) {
if (node->left->priority > node->priority) {
rotLeft(node);
}
if (node->right->priority > node->priority) {
rotRight(node);
}
}
Node* search(Node* &node, int key) {
if (node == _empty)
return _empty;
if (node->key == key)
return node;
if (node->key > key)
return search(node->left, key);
return search(node->right, key);
}
void insert(Node* &node, int key, int freq, int priority) {
if (node == _empty) {
node = new Node(key, freq, priority, freq, _empty, _empty);
return;
}
if (key < node->key || (key == node->key && freq > node->freq)){
insert(node->left, key, freq, priority);
}
else {
insert(node->right, key, freq, priority);
}
updateSize(node);
balance(node);
}
void erase(Node* &node, int key) {
if (node->key > key) {
erase(node->left, key);
updateSize(node);
}
else if (node->key < key) {
erase(node->right, key);
updateSize(node);
}
else {
if (node->left == _empty && node->right == _empty) {
delete node;
node = _empty;
}
else if (node->left->priority > node->right->priority) {
rotLeft(node);
erase(node->right, key);
updateSize(node);
}
else {
rotRight(node);
erase(node->left, key);
updateSize(node);
}
}
}
void addTempRoot(int key) {
insert(root, key, 0, inf);
}
void removeTempRoot() {
root->key = -1;
erase(root, -1);
}
public:
Treap() {
root = _empty = new Node(0, 0, 0, 0, NULL, NULL);
}
void insert(int val, int freq) {
Node* temp = search(root, val);
if (temp == _empty) {
insert(root, val, freq, rand());
}
else {
int newFreq = temp->freq + freq;
erase(root, val);
insert(root, val, newFreq, rand());
}
}
void erase(int val) {
erase(root, val);
}
int query(int val) {
addTempRoot(val);
int ret = root->left->size;
removeTempRoot();
return ret;
}
};
class SegmentTree {
private:
struct Node{
Treap values, exces;
};
vector<Node> segmentTree;
int len, qLeft, qRight, val;
void segUpdate(int node, int left, int right) {
if (left > right)
return;
int intersection = qRight - qLeft + 1;
if (qLeft < left)
intersection -= left - qLeft;
if (right < qRight)
intersection -= qRight - right;
segmentTree[node].values.insert(val, intersection);
if (qLeft <= left && right <= qRight) {
segmentTree[node].exces.insert(val, 1);
return;
}
int middle = (left + right) / 2;
if (middle >= qLeft)
segUpdate(2 * node, left, middle);
if (middle < qRight)
segUpdate(2 * node + 1, middle + 1, right);
}
int segQuery(int node, int left, int right) {
if (qLeft <= left && right <= qRight) {
return segmentTree[node].values.query(val);
}
int middle = (left + right) / 2;
int ret1 = 0, ret2 = 0;
if (middle >= qLeft)
ret1 = segQuery(2 * node, left, middle);
if (middle < qRight)
ret2 = segQuery(2 * node + 1, middle + 1, right);
int intersection = qRight - qLeft + 1;
if (qLeft < left)
intersection -= left - qLeft;
if (right < qRight)
intersection -= qRight - right;
int ret3 = segmentTree[node].exces.query(val) * intersection;
return ret1 + ret2 + ret3;
}
int binarySearch(int left, int right, int pos) {
qLeft = left;
qRight = right;
int binLeft = 1, binRight = 30000;
while (binLeft <= binRight) {
val = (binLeft + binRight) / 2;
int temp = segQuery(1, 1, len);
if (temp < pos)
binLeft = val + 1;
else
binRight = val - 1;
}
if (binLeft == 30001)
return -1;
return binLeft;
}
public:
SegmentTree(int maxLen) {
len = maxLen;
segmentTree.resize(4 * maxLen + 3);
}
void update(int left, int right, int val) {
qLeft = left;
qRight = right;
this->val = val;
segUpdate(1, 1, len);
}
int query(int left, int right, int pos) {
return binarySearch(left, right, pos);
}
};
SegmentTree *segmentTree;
int main() {
srand(time(NULL));
InputReader fin(infile);
ofstream fout(outfile);
int childCount, opCount;
fin >> childCount;
fin >> opCount;
segmentTree = new SegmentTree(childCount);
for (; opCount; --opCount) {
int op, a, b, c;
fin >> op;
fin >> a;
fin >> b;
fin >> c;
++a, ++b;
if (op == 1) {
segmentTree->update(a, b, c);
}
else {
fout << segmentTree->query(a, b, c) << '\n';
}
}
return 0;
}
//Trust me, I'm the Doctor!
Iordache Ioan-Bogdan iordache.bogdan