C1685 [Wannafly冬令营2018Day5]Sorting

你有一个数列 $a_1, a_2, \dots, a_n$，你要模拟一个类似于快速排序的过程。有一个固定的数字 $x$。

你要支持三种操作：

• 询问区间 $[l, r]$ 之间的元素的和，也就是 $\sum_{i=l}^r a_i$。
• 对区间 $[l,r]$ 进行操作，也就是说你把区间中所有的数字拿出来，然后把小于等于 $x$ 的数字按顺序放在左边，把大于 $x$ 的数字按顺序放在右边，把这些数字接起来，放回到数列中。比如说 $x=3$，你的区间里的数字是 $1,5,3,2,4$，那么操作完之后区间里面的数字变为 $1,3,2,5,4$。
• 对区间 $[l,r]$ 进行操作，也就是说你把区间中所有的数字拿出来，然后把大于 $x$ 的数字按顺序放在左边，把小于等于 $x$ 的数字按顺序放在右边，把这些数字接起来，放回到数列中。

样例输入 1

5 9 3
1 5 3 2 4
1 1 5
2 1 5
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
3 3 5
1 1 4

样例输出 1

15
1
3
2
5
4
13