Te iubesc si te ador,
Ghita C. Topor
After reading the book "Baltagul" by Mihail Mihai Sadoveanu, Ucselupaert is very angry at "Evaluatorul infoarena" and decided to beat him at Mortal Kombat 11.
You are given two arrays $$$A$$$ and $$$B$$$ both of length $$$N$$$. We call a pair $$$(i,j)$$$ winning if and only if $$$1 \le i \le j \le N$$$ and $$$max(B_{i...j}) \ge max(A_{i...j})$$$ where $$$i...j$$$ denotes the subarray with left and right endpoints $$$(i,j)$$$. Find the number of winning pairs.
The input consists of a number $$$N$$$ representing the number of elements in the array. On the second and third line there will be the values of $$$A$$$ and $$$B$$$ in this order.
Print one integer : the number of winning pairs.
- $$$N \le 10^6$$$ , $$$-10^9 \le A_i , B_i \le 10^9$$$
- Subtask 1 ( 10 points ) : $$$N \le 10^2$$$
- Subtask 2 ( 10 points ) : $$$N\le 10^3$$$
- Subtask 3 ( 50 points ) : $$$N \le 10^5$$$
- subtask 4 ( 30 ponts ) : no further constrains
5 3 1 4 2 2 5 2 1 3 2
9
I don't mind...
You are given an array $$$A$$$ of $$$N$$$ numbers and an integer $$$T$$$. Find the number of tuples of indices $$$(i,j,k,l)$$$ such that $$$\lfloor \frac{A_i}{A_j} \rfloor + \lfloor \frac{A_k}{A_l} \rfloor$$$ = $$$T$$$.
Two tuples are $$$A$$$ and $$$B$$$ are distinct if there exists some $$$i$$$ such that $$$A_i \neq B_i$$$. For example , (1,1,2,4) is not the same as (1,2,1,4). Note that there may be repetitions.
Print the answer modulo $$$MOD$$$.
The input consists of $$$N$$$,$$$T$$$ and $$$MOD$$$ followed by an array $$$A$$$ of size $$$N$$$.
Print one integer : The number of tuples modulo $$$MOD$$$.
- $$$N \le 10^5$$$ , $$$1 \le A_i \le 5 \cdot 10^5$$$, $$$T \le 5 \cdot 10^5$$$, $$$MOD \le 10^9$$$.
- For test data worth $$$20$$$ points , $$$N \le 50$$$ , $$$1 \le A_i \le 10^5$$$.
- For another $$$20$$$ points, $$$N \le 2000$$$, $$$1 \le A_i \le 10^5$$$.
- For another $$$30$$$ points, $$$1 \le A_i \le 10^5$$$
- For the remaining $$$30$$$ points , there are no further restrictions.
3 2 666013 1 1 1
81
10 2 9821672 372960 389034 286291 199826 189342 219065 129531 340535 69643 177416
2410
In the first sample it is easy to see that every possible tuple is good since $$$\lfloor \frac{1}{1} \rfloor + \lfloor \frac{1}{1} \rfloor = 2$$$. Thus print $$$3^4$$$ mod $$$666013 = 81$$$.
The second sample has a beautiful explination , but unfortunately it is too long to write.
This problem has $$$t$$$ ($$$1 \le t \le 10^5$$$) testcases.
In each testcase you are given two integers $$$N$$$ and $$$M$$$ ($$$1 \le N,M \le 2 \cdot 10^3$$$), and two arrays $$$a=[a_1,a_2,\ldots,a_n]$$$ and $$$b=[b_1,b_2,\ldots,b_m]$$$.
For each testcase, you will have to find any matrix of positive integers $$$ans$$$ with $$$N$$$ rows and $$$M$$$ coloumns which satisfies the following constraints:
- For any row $$$i \in [1,N]$$$, the product of the elements in that row is equal to $$$a_i$$$. More formally, $$$(\forall i \in [1,N])(\prod_{j=1}^M ans_{i,j}=a_i)$$$.
- For any coloumn $$$j \in [1,M]$$$, the product of the elements in that coloumn is equal to $$$b_j$$$. More formally, $$$(\forall j \in [1,M])(\prod_{i=1}^N ans_{i,j}=b_j)$$$.
If there are no matrices satisfying the given constraints, simply print "-1", without the quotes. Otherwise, if there are multiple matrices satisfying the given constraints, you may print any of them.
The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of testcases. The following $$$3\cdot t$$$ lines of input contain the descriptions of the testcases, $$$3$$$ lines per testcase:
The first line of each testcase contains two integers $$$N$$$ and $$$M$$$ ($$$2 \le N,M \le 2 \cdot 10^3$$$).
The second line of each testcase contains $$$N$$$ integers $$$a_1,a_2, \ldots a_n$$$ ($$$1 \le a_i \le 10^9, \forall i \in [1,n]$$$) — the elements of array $$$a$$$.
The third line of each testcase contains $$$M$$$ integers $$$b_1,b_2, \ldots b_m$$$ ($$$1 \le b_i \le 10^9, \forall i \in [1,m]$$$) — the elements of array $$$b$$$.
It is guaranteed that, across all testcases, the sum of $$$N \cdot M$$$ does not exceed $$$5 \cdot 10^6$$$. More formally, it is guaranteed that $$$\sum N \cdot M \le 5 \cdot 10^6$$$.
For each testcase, if there exists some matrix $$$ans$$$ satisfying the given constraints, print $$$N$$$ lines containing the elements of matrix $$$ans$$$, $$$M$$$ integers per line. Otherwise, simply print "-1", without the quotes.
If there are multiple matrices satisfying the given constraints, you may print any of them.
| Group | Additional constraints | Points |
| $$$1$$$ | $$$N=M=2$$$ | $$$8$$$ |
| $$$2$$$ | $$$\sum N \cdot M \le 10^5, a_{i},b_{j} \le 10^5,\forall i,j$$$ | $$$15$$$ |
| $$$3$$$ | $$$\sum N \cdot M \le 10^6, a_{i},b_{j} \le 5 \cdot 10^6,\forall i,j$$$ | $$$13$$$ |
| $$$4$$$ | $$$\sum N \cdot M \le 10^6$$$ | $$$25$$$ |
| $$$5$$$ | — | $$$25$$$ |
3 4 5 20 12 27 15 6 30 45 4 3 3 3 1 1 1 2 1 1 6 5 2808 1 180 1980 1001 945 16632 630 1 23166 3900
2 10 1 1 1 3 1 1 4 1 1 3 9 1 1 1 1 5 1 3 -1 24 9 1 1 13 1 1 1 1 1 9 10 1 2 1 11 1 1 9 20 1 7 1 143 1 7 1 1 9 15
Note that the sample output has extra line breaks for added clarity between consecutive testcases.