Count the Deliveries

লাজিম সম্প্রতি সিদ্ধান্ত নিয়েছে যে একটা পিজ্জা রেস্তোরাঁ খুলবে। তার রেস্তোরাঁর বিশেষত্ব হচ্ছে সে প্রচুর পরিমাণে পিজ্জা ডেলিভারী দিতে পারে। তবে এর জন্য কাস্টোমারদেরকে আগে থেকে পরিমাণ জানিয়ে রাখতে হয়। এরকম অনেকগুলো ডেলিভারী সম্পূর্ণ করার পর, লাজিম জানতে চায় প্রত্যেক কাস্টোমার কে সে কত গুলো করে পিজ্জা পাঠিয়েছে। এবং তোমার কাজ হচ্ছে এটা নির্নয় করা।

লাজিম তোমাকে তার সকল কাস্টোমার রেকর্ড দিয়েছে। শুরুতে, সব কাস্টোমারের অর্ডার পরিমাণ 0 হয়ে আছে। এরপর রেকর্ড গুলো একের পর এক সংগ্রহ করা হয়েছে। দুই ধরনের রেকর্ড রয়েছেঃ

1. $1$ $l$ $r$ $k$ : মানে প্রত্যেক $l \leq i \leq r$ এর জন্য, $i$তম কাস্টোমার তার বর্তমান অর্ডার পরিমাণ $k$ পরিমাণ বাড়িয়েছেন। অর্থাৎ, যদি তার অর্ডার পরিমাণ আগে $x$থেকে থাকে তাহলে এখন তা হয়েছে $x+k$

2. $2$ $l$ $r$ $k$: মানে প্রত্যেক $l \leq i \leq r$ এর জন্য, $i$তম কাস্টোমার $k$বার তার অর্ডার পরিমাণ দিয়ে অর্ডার করেছে। অর্থাৎ, যদি তখন তার অর্ডার পরিমাণ $x$ থেকে থাকে তাহলে সে $k$ বার অর্ডার করে $k \cdot x$টি পিজ্জা ডেলিভারী পেয়েছে।

তুমি সবগুলো রেকর্ড দেখেছো, এখন $1$, $\cdots$, $n$ প্রত্যেক কাস্টোমারের জন্য তোমাকে নির্ণয় করতে হবে লাজিম তাকে কতগুলো পিজ্জা ডেলিভারী দিয়েছে।

Input

ইনপুটের প্রথম লাইনে একটি পূর্ণ সংখ্যা $T$ থাকবে, যা হলো টেস্টকেসের সংখ্যা।

প্রত্যেক টেস্টকেসে, প্রথম লাইনে দুইটি পূর্ণ সংখ্যা $n$ এবং $q$ দেওয়া থাকবে, যা হল কাস্টমারদের সংখ্যা এবং রেকর্ডের সংখ্যা। এরপর $q$ টি রেকর্ড দেওয়া আছে পরবর্তী $q$ টি লাইনে। $i$তম রেকর্ড টি 4টি সংখ্যার মাধ্যমে প্রকাশ করা হয়েছে যারা হল $t$ $l$ $r$ $k$, এখানে $t$এর মান $1$অথবা $2$ উপরের বিবরণীর মত।

Constraints

• $1 \leq T \leq 2\cdot 10^3$

• $1 \leq n, q \leq 10^5$

• $1 \leq t \leq 2$

• $1 \leq l \leq r \leq n$

• $1 \leq k \leq 10^4$

• সকল টেস্টকেসের $n$এর যোগফল $\leq 10^6$

• সকল টেস্টকেসের $q$এর যোগফল $\leq 10^6$

Subtask 1 (5 points) : সকল রেকর্ডের জন্য $l = r$

Subtask 2 (20 points) : প্রথম টাইপের রেকর্ডের জন্য $l = r$, তবে দ্বিতীয় টাইপের রেকর্ডের জন্য $l \neq r$ হতে পারে।

Subtask 3 (75 points) : সকল রেকর্ডের জন্যই $l \neq r$ হতে পারে।

Output

প্রত্যেক টেস্টকেসের জন্য, একটি লাইনে $n$টি পূর্ণ সংখ্যা আউটপুট দিবে। $i$তম সংখ্যাটি $i$তম কাস্টোমারকে ডেলিভারী দেওয়া পিজ্জা পরিমাণ হবে। লক্ষ্য করো যে, উত্তর গুলো 64 বিট signed integer এ প্রকাশ করা যায়।

Sample

Input	Output
2 5 5 1 2 5 10 1 1 4 5 2 1 3 5 2 1 5 2 2 5 5 1 6 10 1 1 6 5 1 4 5 100 2 1 4 5 1 3 6 1 2 2 5 20 2 1 3 10 1 1 6 50 2 3 4 12 1 2 6 15 2 1 4 5	35 105 105 30 30 350 525 1232 5372 2120 0

প্রথম টেস্টে, শুরুতে সবার অর্ডার পরিমাণ 0 তে সেট করা।

1. প্রথম রেকর্ডের পর, কাস্টোমার 2 থেকে 5 তাদের অর্ডার পরিমান 10 বাড়িয়ে দেয়। বর্তমান অর্ডার পরিমানগুলো হলঃ 0 10 10 10 10

2. দ্বিতীয় রেকর্ডের পর, কাস্টোমার 1 থেকে 4 তাদের অর্ডার পরিমাণ 5 বাড়িয়ে দেয়। বর্তমান অর্ডার পরিমানগুলো হলঃ 5 15 15 15 10

3. তৃতীয় রেকর্ডের পর, কাস্টোমার 1 থেকে 3 প্রত্যেকে 5 বার অর্ডার করে। অতএব কাস্টোমার 1, 25টি পিজ্জা পায় এবং কাস্টোমার 2-3, 75টি পিজ্জা পায়। বর্তমান অর্ডার পরিমানগুলো হলঃ 5 15 15 15 10

4. চতুর্থ রেকর্ডের পর, কাস্টোমার 1 থেকে 5 প্রত্যেকে 2 বার অর্ডার করে। অতএব কাস্টোমার 1, 10টি পিজ্জা পায়, কাস্টোমার 2-4, 30টি পিজ্জা পায় এবং কাস্টোমার 5, 20টি পিজ্জা পায়। বর্তমান অর্ডার পরিমানগুলো হলঃ 5 15 15 15 10

5. পঞ্চম রেকর্ডের পর, কাস্টোমার 5, 1 বার অর্ডার করে। অতএব কাস্টোমার 5, 10টি পিজ্জা পায়। বর্তমান অর্ডার পরিমানগুলো হলঃ 5 15 15 15 10

যদি তুমি ডেলিভারী গুলো গণনা করো তাহলে দেখবে যে কাস্টোমার রা 35, 105, 105, 30, 30 টি পিজ্জা ডেলিভারী পেয়েছে। খেয়াল করো, অর্ডার পরিমাণ পরিবর্তনে কোন ডেলিভারি হয় না, শুধু দ্বিতীয় টাইপের রেকর্ডে ডেলিভারি হয়। আবার ডেলিভারি তে অর্ডার এর পরিমাণ পরিবর্তন হয় না।

লক্ষ্য করো যে, স্যাম্পল টি subtask 1 এবং subtask 2 এর অংশ নয়। অতএব subtask 1 এবং subtask 2 এর জন্য তোমার কোড স্যাম্পল এ ঠিকমত কাজ না করলেও হবে।