Description

You have $n$ integers $a[1],a[2],\dots ,a[n]$ and an integer $m$ indicating the operation times. You need to deal with two kinds of operations.

Operation 1:1 p x, do transformation $a[i]=min(a[i],x)(1\le i\le p)$.

Operation 2:2 p x, do transformation $a[i]=min(a[i],x)(p\le i\le n)$.

You only need to output the array $a$ after operations.

Format

Input

The first line of input is an integer $n(1\le n\le 10^{6})$ , an integer $m(1\le n\le 10^{6})$, an integer $k1(1\le k1\le 10^{18})$ and an integer $k2(1\le k2\le 10^{18})$ .

In order to avoid too much input data, the following methods are used to generate data

Output

In order to avoid too much output data, you only need to output the $sum$ of the array $a$ after $m$ times operations .

Samples

5 5 5135616135616484 8646484451351

462653860

Hints

Initialy, aray a is $[527131783415709210,246057301899044788,873328851580452745,322412099270849533,750787086394534891]$ The first operation is $[2,2,249065584865898997]$,the array a transforms to $[527131783415709210,246057301899044788,249065584865898997,249065584865898997,249065584865898997]$ The second operation is $[2,2,948165060176896724]$, the array a transforms to $[527131783415709210,246057301899044788,249065584865898997,249065584865898997,249065584865898997]$ The third operation is $[2,5,271316207691756664]$,the array a transforms to $[527131783415709210,246057301899044788,249065584865898997,249065584865898997,249065584865898997]$ The forth operation is $[1,1,182083963193278158]$, the array a transforms to $[182083963193278158,246057301899044788,249065584865898997,249065584865898997,249065584865898997]$ The fifth operation is $[1,1,595593865170083678]$,the array a transforms to $[182083963193278158,246057301899044788,249065584865898997,249065584865898997,249065584865898997]$ So the sum of the array a after m times operations is $(182083963193278158+246057301899044788+249065584865898997+24906584865898997+249065584865898997)%10000007=462653860$