Find Length of Longest Common Prefix

You are given two arrays arr1 and arr2 of positive integers. Write each integer as its usual decimal string; pick one number from arr1 and one from arr2 and compare their common prefix starting from the most significant digit. Return the length of the longest common prefix over all pairs; if no pair shares a first digit, the result is 0. The prefix may equal one entire number; for example, the common prefix of 123 and 12345 has length 3.

Valid input range on this site: 1≤|arr1|,|arr2|≤50000; 1≤arr[i]≤10^9. The ranges above are added by this site, and the array lengths are on the same scale as the constraints of LeetCode 3043.

输入格式

The first line contains n m; the second line contains n positive integers for arr1; the third line contains m positive integers for arr2.

输出格式

Output the length of the longest common prefix of the decimal representations over all pairs taken from the two arrays.

样例 1

输入：

4 4
123 4 5 955
12345 63 95 2

输出：

3

样例 2

输入：

1 1
7
8

输出：

0

样例 3

输入：

1 1
9
9

输出：

1

样例 4

输入：

1 1
10
1000

输出：

2

样例 5

输入：

2 2
1200 7
1234 12

输出：

2

样例 6

输入：

2 2
1 98
10 99

输出：

1

样例 7

输入：

1 1
999999999
999999999

输出：

9

样例 8

输入：

2 2
2 123456789
2 123456780

输出：

8

样例说明

Store every non-empty prefix of each integer in arr1 in a set, then scan the prefixes of each number in arr2 and update the maximum length. You can stop scanning a number at its first prefix that is not in the set.