AT_abc430_g [ABC430G] Range Set Modifying Query

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.

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 $

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 Explanation 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`. ### 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.