原始题目

Letters

• time limit per test4 seconds
• memory limit per test256 megabytes
• inputstandard input
• outputstandard output

There are n dormitories in Berland State University, they are numbered with integers from 1 to n. Each dormitory consists of rooms, there are ai rooms in i-th dormitory. The rooms in i-th dormitory are numbered from 1 to ai.

A postman delivers letters. Sometimes there is no specific dormitory and room number in it on an envelope. Instead of it only a room number among all rooms of all n dormitories is written on an envelope. In this case, assume that all the rooms are numbered from 1 to a1+a2+⋯+an and the rooms of the first dormitory go first, the rooms of the second dormitory go after them and so on.

For example, in case n=2, a1=3 and a2=5 an envelope can have any integer from 1 to 8 written on it. If the number 7 is written on an envelope, it means that the letter should be delivered to the room number 4 of the second dormitory.

For each of m letters by the room number among all n dormitories, determine the particular dormitory and the room number in a dormitory where this letter should be delivered.

Input

The first line contains two integers n and m (1≤n,m≤2⋅105) — the number of dormitories and the number of letters.

The second line contains a sequence a1,a2,…,an (1≤ai≤1010), where ai equals to the number of rooms in the i-th dormitory. The third line contains a sequence b1,b2,…,bm (1≤bj≤a1+a2+⋯+an), where bj equals to the room number (among all rooms of all dormitories) for the j-th letter. All bj are given in increasing order.

Output

Print m lines. For each letter print two integers f and k — the dormitory number f (1≤f≤n) and the room number k in this dormitory (1≤k≤af) to deliver the letter.

Examples

Input

3 6
10 15 12
1 9 12 23 26 37

Output

1 1
1 9
2 2
2 13
3 1
3 12

Input

2 3
5 10000000000
5 6 9999999999

Output

1 5
2 1
2 9999999994

Note

In the first example letters should be delivered in the following order:

• the first letter in room 1 of the first dormitory
• the second letter in room 9 of the first dormitory
• the third letter in room 2 of the second dormitory
• the fourth letter in room 13 of the second dormitory
• the fifth letter in room 1 of the third dormitory
• the sixth letter in room 12 of the third dormitory

题目大意

给出n个公寓的房间数，给出从第一个房间开始计数的房间号，要求输出按公寓分开后每个房间对应的 公寓号码和在本公寓的房间号码

解题思路

根据n个公寓的房间数处理出前缀和，顺序遍历前缀和数组，对每个查询求差值即可。

解题代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#define eps 1e-8
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
ll gcd(ll a,ll b)
{
	return a?gcd(b%a,a):b;
}

ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
 } 

ll n,m,vis[maxn],ans[maxn],cnt;

ll a[maxn],sum[maxn];

int main()
{
	while(~scanf("%lld%d",&n,&m))
	{
		sum[0]=0;
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld",&sum[i]);
			sum[i]+=sum[i-1]; //处理前缀和	 
		}
		ll temp;
		ll j=0;
		for(ll i=0;i<m;i++)
		{
			scanf("%I64d",&temp);
			while(temp>sum[j]) j++;
			printf("%I64d %I64d\n",j,temp-sum[j-1]);
		}
		
	}
}

收获与反思

前缀和应用。 注意如果查询不按顺序的话应该采用二分查找。