{"code":"antiprefect","name":"Chủ nghĩa không hoàn hảo","description":"Tấn là một người theo chủ nghĩa không hoàn hảo. Anh rất ghét những thứ hoàn hảo, số hoàn hảo cũng không phải ngoại lệ. \r\n\r\nMột số $x$ nguyên dương được gọi là số hoàn hảo, khi: \r\n\r\n$$s(x) = x$$ \r\n\r\nTrọng đó, $s(x)$ là hàm tổng các ước của $x$, không bao gồm $x$. \r\n\r\nMột hôm, anh gặp bài tập về dãy số như sau: \r\n\r\nXét dãy $a$ gồm $n$ số nguyên, ban đầu đều là $0$, thực hiện $q$ truy vấn thuộc $2$ loại sau trên dãy $a$:\r\n \r\n- $1$ $l$ $r$ $v$ : $a_i = v (1 \\le l \\le i \\le r \\le n, 0 \\le v \\le 10^9)$.\r\n- $2$ $l$ $r$ $v$ : $a_i = a_i + v (1 \\le l \\le i \\le r \\le n, 0 \\le v \\le 10^9)$.\r\n\r\nSau khi thực hiện $q$ truy vấn thì in ra mảng $a$.\r\n\r\nTuy nhiên có một vấn đề : Vì Tấn không thích số hoàn hảo, nên dãy $a$ không được có sự xuất hiện của số hoàn hảo. Vậy nên khi thực hiện truy vấn $i$, nếu trong dãy có số hoàn hảo xuất hiện, thực hiện tăng các số có vị trí từ $l_i . . . r_i$ của dãy $a$ lên $1$ liên tục cho đến khi dãy không còn số hoàn hảo nào. \r\n\r\nTuy nhiên việc này vô tình khiến bài toán trở nên khó hơn rất nhiều. Hơn nữa Tấn đang cần học bài để thi kiểm tra trên lớp. Các bạn hãy giúp Tấn giải bài toán nhé. \r\n\r\n

Input

\r\n\r\n- Dòng đầu nhập 2 số $n$ và $q$ lần lượt là số phần tử của dãy $a$ và số truy vấn. $(1 \\le n, q \\le 10^5)$.\r\n- $q$ dòng tiếp theo, mỗi dòng nhập vào $4$ số nguyên dương $type$ $l$ $r$ $v$ $(1 \\le type \\le 2)$.\r\n\r\n

Output

\r\n\r\n- In ra mảng sau khi thực hiện $q$ truy vấn.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ (40% số điểm): $n, q \\le 10^3$ \r\n- Subtask $2$ (60% số điểm): Không có ràng buộc gì thêm\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 5 7\r\n 2 1 5 1 \r\n 2 2 5 1 \r\n 2 3 5 1 \r\n 2 4 5 1 \r\n 2 5 5 1 \r\n 2 3 5 1 \r\n 1 1 3 28 \r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 29 29 29 8 9\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n **Lưu ý:** Các số được in đậm là các số hoàn hảo.\r\n \r\n - Sau truy vấn thứ $5$, a = [1, 2, 3, 4, 5].\r\n - Sau truy vấn thứ $6$, a = [1, 2, 4, 5, **6**]. Vì $a_5$ là số hoàn hảo, Dế Mèn thực hiện tăng 1 lên các số có vị trí từ 3 đến 5 : [1, 2, 4, 5, **6**] -> [1, 2, 5, **6**, 7] -> [1, 2, **6**, 7, 8] -> [1, 2, 7, 8, 9]. \r\n - Sau truy vấn thứ $7$, a = [**28**, **28**, **28**, 8, 9], vì xuất hiện số hoàn hảo, Dế Mèn thực hiện tăng 1 lên các số có vị trí từ 1 đến 3 : [**28**, **28**, **28**, 8, 9] -> [29, 29, 29, 8, 9].","points":550.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}