G - Range Set Modifying Query 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 625 点

問題文

N 個の集合 S_1, \ldots,S_N があります。最初、全ての集合は空集合です。

以下の形式のクエリが Q 個与えられるので順に処理してください。

  • タイプ 1：1 L R x の形式で与えられる。L \leq i \leq R を満たす各 S_i に対し、x を追加する。
  • タイプ 2：2 L R x の形式で与えられる。L \leq i \leq R を満たす各 S_i に対し、x を削除する。
  • タイプ 3：3 L R の形式で与えられる。L \leq i \leq R を満たす S_i のうちの、要素数の最大値と、それを達成する集合の個数を求める。

制約

  • 1\leq N \leq 3\times 10^5
  • 1\leq Q \leq 3\times 10^5
  • 各クエリにおいて、1 \leq L \leq R \leq N
  • タイプ 1,2 のクエリにおいて、1 \leq x \leq 60
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

ただし、\mathrm{query}_i は i 番目のクエリを表し、それぞれ問題文中に示した以下の形式で与えられる。

1 L R x

2 L R x

3 L R

出力

タイプ 3 のクエリの個数を q として q 行出力せよ。
i 行目には、i 個目のタイプ 3 のクエリにおいて、要素数の最大値を x、それを達成する集合の個数を y として、x,y を空白区切りで出力せよ。

入力例 1

4 7
1 1 2 10
1 2 4 20
3 1 3
2 1 2 20
1 2 3 10
3 1 2
3 1 4

出力例 1

2 1
1 2
2 1
  • 最初 (S_1,S_2,S_3,S_4)=(\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace) です。
  • 1 番目のクエリにより S_1,S_2 に 10 が追加され、(S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace\rbrace,\lbrace\rbrace) となります。
  • 2 番目のクエリにより S_2,S_3,S_4 に 20 が追加され、(S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10,20\rbrace,\lbrace 20\rbrace,\lbrace 20\rbrace) となります。
  • 3 番目のクエリにおいて、S_1,S_2,S_3 のうち要素数が最大となるのは S_2 の 2 個であるため、2 1 を出力します。
  • 4 番目のクエリにより S_1,S_2 から 20 が削除され、(S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace 20\rbrace,\lbrace 20\rbrace) となります。
  • 5 番目のクエリにより S_2,S_3 に 10 が追加され、(S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace 10,20\rbrace,\lbrace 20\rbrace) となります。
  • 6 番目のクエリにおいて、S_1,S_2 のうち要素数が最大となるのは S_1,S_2 の 1 個であるため、1 2 を出力します。
  • 7 番目のクエリにおいて、S_1,S_2,S_3,S_4 のうち要素数が最大となるのは S_3 の 2 個であるため、2 1 を出力します。

Score : 625 points

Problem Statement

There are N sets S_1, \ldots,S_N. Initially, all sets are empty.

You are given Q queries in the following formats. Process them in order.

  • Type 1: Given as 1 L R x. For each S_i satisfying L \leq i \leq R, add x.
  • Type 2: Given as 2 L R x. For each S_i satisfying L \leq i \leq R, remove x.
  • Type 3: Given as 3 L R. Find the maximum number of elements among S_i satisfying L \leq i \leq R, and the number of sets that achieve this maximum.

Constraints

  • 1\leq N \leq 3\times 10^5
  • 1\leq Q \leq 3\times 10^5
  • For each query, 1 \leq L \leq R \leq N.
  • For type 1,2 queries, 1 \leq x \leq 60.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Here, \mathrm{query}_i represents the i-th query, and each is given in one of the following formats as shown in the problem statement:

1 L R x

2 L R x

3 L R

Output

Let q be the number of type 3 queries, and print q lines.
The i-th line should contain x,y separated by a space, where x is the maximum number of elements and y is the number of sets that achieve this maximum for the i-th type 3 query.

Sample Input 1

4 7
1 1 2 10
1 2 4 20
3 1 3
2 1 2 20
1 2 3 10
3 1 2
3 1 4

Sample Output 1

2 1
1 2
2 1
  • Initially (S_1,S_2,S_3,S_4)=(\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace,\lbrace\rbrace).
  • The 1-st query adds 10 to S_1,S_2, resulting in (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace\rbrace,\lbrace\rbrace).
  • The 2-nd query adds 20 to S_2,S_3,S_4, resulting in (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10,20\rbrace,\lbrace 20\rbrace,\lbrace 20\rbrace).
  • For the 3-rd query, the maximum number of elements among S_1,S_2,S_3 is 2 achieved by S_2, so print 2 1.
  • The 4-th query removes 20 from S_1,S_2, resulting in (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace 20\rbrace,\lbrace 20\rbrace).
  • The 5-th query adds 10 to S_2,S_3, resulting in (S_1,S_2,S_3,S_4)=(\lbrace 10\rbrace,\lbrace 10\rbrace,\lbrace 10,20\rbrace,\lbrace 20\rbrace).
  • For the 6-th query, the maximum number of elements among S_1,S_2 is 1 achieved by S_1,S_2, so print 1 2.
  • For the 7-th query, the maximum number of elements among S_1,S_2,S_3,S_4 is 2 achieved by S_3, so print 2 1.