Get Total Requests

There are initially n servers, and each server's ID is also the number of requests it handles. Over the next n days, on day j every server with ID replaced[j] changes its ID to newId[j]; output the sum of IDs after each day's operation. Replacing an ID that does not exist, or replacing an ID with itself, leaves the result unchanged.

输入格式

The first line contains n, followed by three lines of n integers each: the initial IDs, replaced, and newId. The raw ranges are written as 105 and 104 without superscripts; this site explicitly uses 1≤n≤100000 and 1≤every ID≤10000.

输出格式

Output n integers, the total requests after each day's operation.

样例 1

输入：

2
20 10
10 20
20 1

输出：

40 2

样例 2

输入：

2
3 3
3 1
1 5

输出：

2 10

样例 3

输入：

3
2 5 2
2 5 3
3 1 5

输出：

11 7 11

样例说明

The answers are 40 2, 2 10 and 11 7 11; a replacement also affects servers whose IDs were already changed on an earlier day.