网站包含各种元素，包括可见的 UI 元素和不可见的组合框架。正如你在 DOMjudge 团队的界面上所见，它可以被划分为多个组件。这些区域以层次化的树状结构组织，称为 DOM 树，尽管它们之间并非直接相关。

你是一个全新浏览器项目的开发者。在该项目中，元素被建模为放置在笛卡尔平面上的矩形，且它们以适当的方式嵌套。也就是说，每一对矩形要么严格包含对方，要么完全不相交。

当前的算法按迭代运行：浏览器在单次迭代中渲染最外层的元素（即不被任何其他元素包含的元素）。这些元素被标记为已完成，并在后续迭代中被忽略。此过程重复进行，直到所有元素都被渲染。因此，浏览器将一个元素的渲染深度（render depth）定义为所有严格包含它的其他元素中最大渲染深度加一；如果没有这样的元素，则渲染深度为零。

然而，现代网站通常包含更多动画，这使得当前的渲染算法不堪重负。为了识别性能瓶颈，你的团队需要一个工具来实时分析网站结构。每个元素都有一个动画开关，用于控制它是否显示动画。为了更好地查看页面，元素的一个关键属性是它是否包含任何显示动画的部分。因此，如果一个元素包含某些（包括自身在内的）动画开关开启的元素，则称该元素为“动画元素”（animated）。

为了衡量渲染过程的一次迭代可能有多慢，你需要负责监控每次迭代的资源使用情况。更具体地说，你需要处理动画开关的切换，并回答询问给定渲染深度的动画元素数量的查询。

输入格式

输入的第一行包含两个整数 $n$ ($1 \le n \le 5 \times 10^5$) 和 $q$ ($1 \le q \le 5 \times 10^5$)，其中 $n$ 是元素数量，$q$ 是即将发生的事件总数。

接下来的 $n$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$ ($1 \le x_1 < x_2 \le 10^9, 1 \le y_1 < y_2 \le 10^9$)，表示一个左下角为 $(x_1, y_1)$、右上角为 $(x_2, y_2)$ 的矩形元素。矩形的边界互不相交，甚至在点上也不相交。

随后是 $q$ 行，按时间顺序表示事件。每行格式为 ^ i 或 ? k。第一种格式表示第 $i$ 个元素（$1 \le i \le n$，按输入顺序）的动画开关应被切换，即开启变为关闭，反之亦然。第二种格式表示查询渲染深度为 $k$ ($0 \le k$) 的动画元素数量。

初始时，所有动画开关均为关闭状态，且至少包含一个第二种格式的事件。查询中指定的渲染深度不会超过所有元素的最大渲染深度。

输出格式

对于每个查询，输出一行，包含给定渲染深度的动画元素数量。

样例

输入 1

8 7
1 1 15 11
2 2 7 4
2 5 7 10
3 6 4 9
5 6 6 7
8 2 14 10
9 5 13 9
11 6 12 7
^ 4
^ 5
^ 8
? 0
? 1
? 2
? 3

输出 1

1
2
3
1