English · Original
Chinese · Translation
Formal · Original
Leha like all kinds of strange things. Recently he liked the function _F_(_n_, _k_). Consider all possible _k_\-element subsets of the set \[1, 2, ..., _n_\]. For subset find minimal element in it. _F_(_n_, _k_) — mathematical expectation of the minimal element among all _k_\-element subsets.
But only function does not interest him. He wants to do interesting things with it. Mom brought him two arrays _A_ and _B_, each consists of _m_ integers. For all _i_, _j_ such that 1 ≤ _i_, _j_ ≤ _m_ the condition _A__i_ ≥ _B__j_ holds. Help Leha rearrange the numbers in the array _A_ so that the sum is maximally possible, where _A_' is already rearranged array.
## Input
First line of input data contains single integer _m_ (1 ≤ _m_ ≤ 2·105) — length of arrays _A_ and _B_.
Next line contains _m_ integers _a_1, _a_2, ..., _a__m_ (1 ≤ _a__i_ ≤ 109) — array _A_.
Next line contains _m_ integers _b_1, _b_2, ..., _b__m_ (1 ≤ _b__i_ ≤ 109) — array _B_.
## Output
Output _m_ integers _a_'1, _a_'2, ..., _a_'_m_ — array _A_' which is permutation of the array _A_.
[samples]
Leha 喜欢所有奇怪的事物。最近，他喜欢上了函数 $F(n, k)$。考虑集合 $[1, 2, ..., n]$ 的所有可能的 $k$-元素子集。对于每个子集，找出其中的最小元素。$F(n, k)$ 表示所有 $k$-元素子集中最小元素的数学期望。
但仅仅函数本身并不能让他满足。他想用它做一些有趣的事情。妈妈给他带来了两个数组 $A$ 和 $B$，每个数组都包含 $m$ 个整数。对于所有满足 $1 ≤ i, j ≤ m$ 的 $i, j$，都有条件 $A_i ≥ B_j$ 成立。请帮助 Leha 重新排列数组 $A$ 中的数字，使得和 $\sum_{i=1}^{m} F(A'_i, B_i)$ 尽可能大，其中 $A'$ 是重新排列后的数组。
输入数据的第一行包含一个整数 $m$（$1 ≤ m ≤ 2·10^5$）——数组 $A$ 和 $B$ 的长度。
接下来一行包含 $m$ 个整数 $a_1, a_2, ..., a_m$（$1 ≤ a_i ≤ 10^9$）——数组 $A$。
接下来一行包含 $m$ 个整数 $b_1, b_2, ..., b_m$（$1 ≤ b_i ≤ 10^9$）——数组 $B$。
请输出 $m$ 个整数 $a'_1, a'_2, ..., a'_m$ —— 数组 $A'$，它是数组 $A$ 的一个排列。
## Input
输入数据的第一行包含一个整数 $m$（$1 ≤ m ≤ 2·10^5$）——数组 $A$ 和 $B$ 的长度。接下来一行包含 $m$ 个整数 $a_1, a_2, ..., a_m$（$1 ≤ a_i ≤ 10^9$）——数组 $A$。接下来一行包含 $m$ 个整数 $b_1, b_2, ..., b_m$（$1 ≤ b_i ≤ 10^9$）——数组 $B$。
## Output
请输出 $m$ 个整数 $a'_1, a'_2, ..., a'_m$ —— 数组 $A'$，它是数组 $A$ 的一个排列。
[samples]
**Definitions**
Let $ m \in \mathbb{Z}^+ $ be the length of arrays $ A $ and $ B $.
Let $ A = (a_1, a_2, \dots, a_m) $ and $ B = (b_1, b_2, \dots, b_m) $ be sequences of positive integers.
Let $ A' = (a'_1, a'_2, \dots, a'_m) $ be a permutation of $ A $.
**Constraints**
1. $ 1 \leq m \leq 2 \cdot 10^5 $
2. $ 1 \leq a_i, b_j \leq 10^9 $ for all $ i, j \in \{1, \dots, m\} $
3. $ \forall i, j \in \{1, \dots, m\}, \; a_i \geq b_j $
**Objective**
Find a permutation $ A' $ of $ A $ that maximizes the sum:
$$
\sum_{i=1}^m F(a'_i, b_i)
$$
where $ F(n, k) $ denotes the expected value of the minimum element over all $ k $-element subsets of $ \{1, 2, \dots, n\} $.
**Note**: The function $ F(n, k) $ is given by:
$$
F(n, k) = \frac{n+1}{k+1}
$$
API Response (JSON)
{
"problem": {
"name": "C. Leha and Function",
"description": {
"content": "Leha like all kinds of strange things. Recently he liked the function _F_(_n_, _k_). Consider all possible _k_\\-element subsets of the set \\[1, 2, ..., _n_\\]. For subset find minimal element in it. _F",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF841C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Leha like all kinds of strange things. Recently he liked the function _F_(_n_, _k_). Consider all possible _k_\\-element subsets of the set \\[1, 2, ..., _n_\\]. For subset find minimal element in it. _F...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Leha 喜欢所有奇怪的事物。最近，他喜欢上了函数 $F(n, k)$。考虑集合 $[1, 2, ..., n]$ 的所有可能的 $k$-元素子集。对于每个子集，找出其中的最小元素。$F(n, k)$ 表示所有 $k$-元素子集中最小元素的数学期望。\n\n但仅仅函数本身并不能让他满足。他想用它做一些有趣的事情。妈妈给他带来了两个数组 $A$ 和 $B$，每个数组都包含 $m$ 个整数。对于所有满足 ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ m \\in \\mathbb{Z}^+ $ be the length of arrays $ A $ and $ B $. \nLet $ A = (a_1, a_2, \\dots, a_m) $ and $ B = (b_1, b_2, \\dots, b_m) $ be sequences of positive integers. \nLet $...",
"is_translate": false,
"language": "Formal"
}
]
}