2

Medium

Given two non-empty linked lists that represent non-negative integers, where the digits are stored in reverse order and each node contains a single digit, the task is to add the two numbers and return the sum as a linked list. It is assumed that the two numbers do not contain any leading zeros, except for the number 0 itself.

Input Format

Integers n and m represent the sizes of the two linked lists, respectively.
Next, n integers represent the values of the nodes in the first linked list.
Finally, m integers represent the values of the nodes in the second linked list.

Output Format

Print the linked list that represents the addition of the two input linked lists OR return the head of the new linked list that contains the sum of the two input lists.

Example

Input

2 2 1 1 3 3

Output

4 4

Constraints

The linked lists provided have a length between 1 and 100 nodes, inclusive.
Each node's value is between 0 and 9, inclusive.
The linked lists represent non-negative integers and do not have leading zeros.