Blake is a CEO of a large company called "Blake Technologies". He loves his company very much and he thinks that his company should be the best. That is why every candidate needs to pass through the interview that consists of the following problem.
We define function f(x, l, r) as a bitwise OR of integers xl, xl + 1, ..., xr, where xi is the i-th element of the array x. You are given two arrays a and b of length n. You need to determine the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n.
The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the length of the arrays.
The second line contains n integers ai (0 ≤ ai ≤ 109).
The third line contains n integers bi (0 ≤ bi ≤ 109).
Print a single integer — the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n.
5
1 2 4 3 2
2 3 3 12 1
22
10
13 2 7 11 8 4 9 8 5 1
5 7 18 9 2 3 0 11 8 6
46
Bitwise OR of two non-negative integers a and b is the number c = a OR b, such that each of its digits in binary notation is 1 if and only if at least one of a or b have 1 in the corresponding position in binary notation.
In the first sample, one of the optimal answers is l = 2 and r = 4, because f(a, 2, 4) + f(b, 2, 4) = (2 OR 4 OR 3) + (3 OR 3 OR 12) = 7 + 15 = 22. Other ways to get maximum value is to choose l = 1 and r = 4, l = 1 and r = 5, l = 2 and r = 4, l = 2 and r = 5, l = 3 and r = 4, or l = 3 and r = 5.
In the second sample, the maximum value is obtained for l = 1 and r = 9.
Kris works in a large company "Blake Technologies". As a best engineer of the company he was assigned a task to develop a printer that will be able to print horizontal and vertical strips. First prototype is already built and Kris wants to tests it. He wants you to implement the program that checks the result of the printing.
Printer works with a rectangular sheet of paper of size n × m. Consider the list as a table consisting of n rows and m columns. Rows are numbered from top to bottom with integers from 1 to n, while columns are numbered from left to right with integers from 1 to m. Initially, all cells are painted in color 0.
Your program has to support two operations:
- Paint all cells in row ri in color ai;
- Paint all cells in column ci in color ai.
If during some operation i there is a cell that have already been painted, the color of this cell also changes to ai.
Your program has to print the resulting table after k operation.
The first line of the input contains three integers n, m and k (1 ≤ n, m ≤ 5000, n·m ≤ 100 000, 1 ≤ k ≤ 100 000) — the dimensions of the sheet and the number of operations, respectively.
Each of the next k lines contains the description of exactly one query:
- 1 ri ai (1 ≤ ri ≤ n, 1 ≤ ai ≤ 109), means that row ri is painted in color ai;
- 2 ci ai (1 ≤ ci ≤ m, 1 ≤ ai ≤ 109), means that column ci is painted in color ai.
Print n lines containing m integers each — the resulting table after all operations are applied.
3 3 3
1 1 3
2 2 1
1 2 2
3 1 3
2 2 2
0 1 0
5 3 5
1 1 1
1 3 1
1 5 1
2 1 1
2 3 1
1 1 1
1 0 1
1 1 1
1 0 1
1 1 1
The figure below shows all three operations for the first sample step by step. The cells that were painted on the corresponding step are marked gray.
Each month Blake gets the report containing main economic indicators of the company "Blake Technologies". There are n commodities produced by the company. For each of them there is exactly one integer in the final report, that denotes corresponding revenue. Before the report gets to Blake, it passes through the hands of m managers. Each of them may reorder the elements in some order. Namely, the i-th manager either sorts first ri numbers in non-descending or non-ascending order and then passes the report to the manager i + 1, or directly to Blake (if this manager has number i = m).
Employees of the "Blake Technologies" are preparing the report right now. You know the initial sequence ai of length n and the description of each manager, that is value ri and his favourite order. You are asked to speed up the process and determine how the final report will look like.
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of commodities in the report and the number of managers, respectively.
The second line contains n integers ai (|ai| ≤ 109) — the initial report before it gets to the first manager.
Then follow m lines with the descriptions of the operations managers are going to perform. The i-th of these lines contains two integers ti and ri (
, 1 ≤ ri ≤ n), meaning that the i-th manager sorts the first ri numbers either in the non-descending (if ti = 1) or non-ascending (if ti = 2) order.
Print n integers — the final report, which will be passed to Blake by manager number m.
3 1
1 2 3
2 2
2 1 3
4 2
1 2 4 3
2 3
1 2
2 4 1 3
In the first sample, the initial report looked like: 1 2 3. After the first manager the first two numbers were transposed: 2 1 3. The report got to Blake in this form.
In the second sample the original report was like this: 1 2 4 3. After the first manager the report changed to: 4 2 1 3. After the second manager the report changed to: 2 4 1 3. This report was handed over to Blake.
Each employee of the "Blake Techologies" company uses a special messaging app "Blake Messenger". All the stuff likes this app and uses it constantly. However, some important futures are missing. For example, many users want to be able to search through the message history. It was already announced that the new feature will appear in the nearest update, when developers faced some troubles that only you may help them to solve.
All the messages are represented as a strings consisting of only lowercase English letters. In order to reduce the network load strings are represented in the special compressed form. Compression algorithm works as follows: string is represented as a concatenation of n blocks, each block containing only equal characters. One block may be described as a pair (li, ci), where li is the length of the i-th block and ci is the corresponding letter. Thus, the string s may be written as the sequence of pairs 
.
Your task is to write the program, that given two compressed string t and s finds all occurrences of s in t. Developers know that there may be many such occurrences, so they only ask you to find the number of them. Note that p is the starting position of some occurrence of s in t if and only if tptp + 1...tp + |s| - 1 = s, where ti is the i-th character of string t.
Note that the way to represent the string in compressed form may not be unique. For example string "aaaa" may be given as 
, 
, 
...
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of blocks in the strings t and s, respectively.
The second line contains the descriptions of n parts of string t in the format "li-ci" (1 ≤ li ≤ 1 000 000) — the length of the i-th part and the corresponding lowercase English letter.
The second line contains the descriptions of m parts of string s in the format "li-ci" (1 ≤ li ≤ 1 000 000) — the length of the i-th part and the corresponding lowercase English letter.
Print a single integer — the number of occurrences of s in t.
5 3
3-a 2-b 4-c 3-a 2-c
2-a 2-b 1-c
1
6 1
3-a 6-b 7-a 4-c 8-e 2-a
3-a
6
5 5
1-h 1-e 1-l 1-l 1-o
1-w 1-o 1-r 1-l 1-d
0
In the first sample, t = "aaabbccccaaacc", and string s = "aabbc". The only occurrence of string s in string t starts at position p = 2.
In the second sample, t = "aaabbbbbbaaaaaaacccceeeeeeeeaa", and s = "aaa". The occurrences of s in t start at positions p = 1, p = 10, p = 11, p = 12, p = 13 and p = 14.
Blake is the boss of Kris, however, this doesn't spoil their friendship. They often gather at the bar to talk about intriguing problems about maximising some values. This time the problem is really special.
You are given an array a of length n. The characteristic of this array is the value 
— the sum of the products of the values ai by i. One may perform the following operation exactly once: pick some element of the array and move to any position. In particular, it's allowed to move the element to the beginning or to the end of the array. Also, it's allowed to put it back to the initial position. The goal is to get the array with the maximum possible value of characteristic.
The first line of the input contains a single integer n (2 ≤ n ≤ 200 000) — the size of the array a.
The second line contains n integers ai (1 ≤ i ≤ n, |ai| ≤ 1 000 000) — the elements of the array a.
Print a single integer — the maximum possible value of characteristic of a that can be obtained by performing no more than one move.
4
4 3 2 5
39
5
1 1 2 7 1
49
3
1 1 2
9
In the first sample, one may pick the first element and place it before the third (before 5). Thus, the answer will be 3·1 + 2·2 + 4·3 + 5·4 = 39.
In the second sample, one may pick the fifth element of the array and place it before the third. The answer will be 1·1 + 1·2 + 1·3 + 2·4 + 7·5 = 49.