CodeForces978C Letters（模拟）

59 阅读 0 评论 39 点赞

我是靠谱客的博主冷傲犀牛，最近开发中收集的这篇文章主要介绍CodeForces978C Letters（模拟），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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 ndormitories 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 1to 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

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,m。有n个宿舍楼以及每个宿舍的房间数，把所有房间号按1到a1+a2+...+an编号。再给出m次询问，每次询问一个编号，问这个编号是第几个宿舍楼的第几个宿舍。m个询问按递增顺序给出。

解题思路：

因为按递增顺序给出，所以每找一次就可以存下当前找到的sum和对应的下标，下次找直接在这个基础上继续找下去就行了。

AC代码：

#include<stdio.h>

typedef long long ll;

int main()
{
	ll n,m;
	while(~scanf("%lld%lld",&n,&m))
	{
		ll a[n];
		for(ll i=0;i<n;i++)
		{
			scanf("%lld",&a[i]);
		}
		ll sum=0,x; 
		int f=0,i;//记录下标避免重复查找 
		while(m--)
		{
			scanf("%lld",&x);//按递增顺序给出 
			x-=sum;
			for(i=f;i<n;i++)
			{
				if(x-a[i]>0)
				{
					x-=a[i];
					sum+=a[i];
				}
				else
				{
					printf("%d %lldn",i+1,x);
					f=i;
					break;
				}
			}
		}
	}
	return 0;
}