using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("2 4");
WillReturn.Add("1 3 6 10");
WillReturn.Add("3 6 6 20");
WillReturn.Add("4 7");
WillReturn.Add("-1 -1");
WillReturn.Add("1 4");
WillReturn.Add("7 13");
//30
//0
//10
//0
}
else if (InputPattern == "Input2") {
WillReturn.Add("2 3");
WillReturn.Add("-3 5 4 100");
WillReturn.Add("1 9 7 30");
WillReturn.Add("1 9");
WillReturn.Add("1 8");
WillReturn.Add("8 10");
//130
//100
//30
}
else if (InputPattern == "Input3") {
WillReturn.Add("10 10");
WillReturn.Add("17 2 17 1000000000");
WillReturn.Add("7 12 12 1000000000");
WillReturn.Add("2 12 8 1000000000");
WillReturn.Add("2 12 2 1000000000");
WillReturn.Add("3 9 16 1000000000");
WillReturn.Add("8 13 15 1000000000");
WillReturn.Add("8 1 3 1000000000");
WillReturn.Add("15 9 17 1000000000");
WillReturn.Add("16 5 5 1000000000");
WillReturn.Add("13 12 9 1000000000");
WillReturn.Add("17 3");
WillReturn.Add("4 10");
WillReturn.Add("1 9");
WillReturn.Add("5 3");
WillReturn.Add("17 12");
WillReturn.Add("14 19");
WillReturn.Add("19 17");
WillReturn.Add("17 11");
WillReturn.Add("16 17");
WillReturn.Add("12 16");
//1000000000
//1000000000
//0
//0
//5000000000
//4000000000
//6000000000
//3000000000
//5000000000
//3000000000
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
class EventInfoDef
{
internal long Type; // 1(コスト区間の追加) 2(問い合わせ) 3(コスト区間の削除)
internal long X; // クエリ1,2,3
internal long StaY; // クエリ1,3
internal long EndY; // クエリ1,3
internal long Cost; // クエリ1,3
internal long SortKey; // クエリ2
internal long Y; // クエリ2
internal long Answer; // クエリ2
}
static List<EventInfoDef> mEventInfoList = new List<EventInfoDef>();
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(InputList[0]);
long N = wkArr[0];
foreach (string EachStr in InputList.Skip(1).Take((int)N)) {
SplitAct(EachStr);
long XMin = wkArr[0];
long YMin = wkArr[1];
long D = wkArr[2];
long C = wkArr[3];
EventInfoDef WillAdd1 = new EventInfoDef();
WillAdd1.Type = 1;
WillAdd1.X = XMin;
WillAdd1.StaY = YMin;
WillAdd1.EndY = YMin + D;
WillAdd1.Cost = C;
mEventInfoList.Add(WillAdd1);
EventInfoDef WillAdd2 = new EventInfoDef();
WillAdd2.Type = 3;
WillAdd2.X = XMin + D;
WillAdd2.StaY = YMin;
WillAdd2.EndY = YMin + D;
WillAdd2.Cost = -C;
mEventInfoList.Add(WillAdd2);
}
foreach (string EachStr in InputList.Skip(1 + (int)N)) {
SplitAct(EachStr);
EventInfoDef WillAdd3 = new EventInfoDef();
WillAdd3.Type = 2;
WillAdd3.X = wkArr[0];
WillAdd3.SortKey = mEventInfoList.Count;
WillAdd3.Y = wkArr[1];
mEventInfoList.Add(WillAdd3);
}
mEventInfoList = mEventInfoList.OrderBy(pX => pX.X).ThenBy(pX => pX.Type).ToList();
// Y座標を座標圧縮する
var YSet = new HashSet<long>();
foreach (EventInfoDef EachEventInfo in mEventInfoList) {
YSet.Add(EachEventInfo.StaY);
YSet.Add(EachEventInfo.EndY);
YSet.Add(EachEventInfo.Y);
}
Dictionary<long, long> ZaatuDict = DeriveZaatuDict(YSet);
var InsDualSegmentTree = new DualSegmentTree(ZaatuDict.Count - 1);
for (int I = 0; I <= mEventInfoList.Count - 1; I++) {
EventInfoDef EachEventInfo = mEventInfoList[I];
if (EachEventInfo.Type == 1 || EachEventInfo.Type == 3) {
long StaY = ZaatuDict[EachEventInfo.StaY];
long EndY = ZaatuDict[EachEventInfo.EndY];
long Cost = EachEventInfo.Cost;
InsDualSegmentTree.RangeAdd(StaY, EndY, Cost);
}
if (EachEventInfo.Type == 2) {
long Y = ZaatuDict[EachEventInfo.Y];
long Answer = InsDualSegmentTree[Y];
EachEventInfo.Answer = Answer;
}
}
foreach (EventInfoDef EachEventInfo in mEventInfoList.OrderBy(pX => pX.SortKey)) {
if (EachEventInfo.Type == 2) {
Console.WriteLine(EachEventInfo.Answer);
}
}
}
//////////////////////////////////////////////////////////////////////////
// 列挙を引数として、座標圧縮し、座圧後の値[座圧前の値]なDictを返す
//////////////////////////////////////////////////////////////////////////
static Dictionary<long, long> DeriveZaatuDict(IEnumerable<long> pEnum)
{
var ZaatuDict = new Dictionary<long, long>();
var ValSet = new HashSet<long>(pEnum);
long No = 0;
foreach (long EachVal in ValSet.OrderBy(pX => pX)) {
ZaatuDict[EachVal] = No;
No++;
}
return ZaatuDict;
}
}
// 区間加算、1点取得な双対セグ木(フェニック木使用)
#region DualSegmentTree
internal class DualSegmentTree
{
private long[] mBitArr; // 内部配列(1オリジンなため、添字0は未使用)
private long mExternalArrUB;
// ノードのIndexの列挙を返す
internal IEnumerable<long> GetNodeIndEnum()
{
for (long I = 0; I <= GetUB(); I++) {
yield return I;
}
}
// ノードのUBを返す
internal long GetUB()
{
return mExternalArrUB;
}
// コンストラクタ
// フェニック木の外部配列(0オリジン)のUBを指定
internal DualSegmentTree(long pExternalArrUB)
{
mExternalArrUB = pExternalArrUB;
// フェニック木の外部配列は0オリジンで、
// フェニック木の内部配列は1オリジンなため、2を足す
mBitArr = new long[pExternalArrUB + 2];
}
// インデクサ
internal long this[long pInd]
{
get { return GetVal(pInd); }
set { RangeAdd(pInd, pInd, value - GetVal(pInd)); }
}
// 双対セグメント木の機能
// 区間加算
internal void RangeAdd(long pSta, long pEnd, long AddVal)
{
pSta++; // 1オリジンに変更
pEnd++; // 1オリジンに変更
long ImosSta = pSta;
long ImosEnd = pEnd + 1;
// いもす法
FenwickTree_Add(ImosSta, AddVal);
if (ImosEnd <= mBitArr.GetUpperBound(0)) {
FenwickTree_Add(ImosEnd, -AddVal);
}
}
// 双対セグメント木の機能
// 1点取得
internal long GetVal(long pInd)
{
pInd++; // 1オリジンに変更
return FenwickTree_GetSum(1, pInd);
}
// フェニック木の機能
// [pSta,pEnd] のSumを返す
private long FenwickTree_GetSum(long pSta, long pEnd)
{
return FenwickTree_GetSum(pEnd) - FenwickTree_GetSum(pSta - 1);
}
// フェニック木の機能
// [0,pEnd] のSumを返す
private long FenwickTree_GetSum(long pEnd)
{
long Sum = 0;
while (pEnd >= 1) {
Sum += mBitArr[pEnd];
pEnd -= pEnd & -pEnd;
}
return Sum;
}
// フェニック木の機能
// [I] に Xを加算
private void FenwickTree_Add(long pI, long pX)
{
while (pI <= mBitArr.GetUpperBound(0)) {
mBitArr[pI] += pX;
pI += pI & -pI;
}
}
}
#endregion