Harry Potter and the Deathly Hallows  2

All submissions for this problem are available.
"Give me Harry Potter. Do this and none shall be harmed. Give me Harry Potter, and I shall leave Hogwarts untouched. Give me Harry Potter, and you will be rewarded."
Harry has only few people left to support him. In this crucial time, he needs to find people with greater strength. Given some information about people, Harry has to find strength of each individual.
Every person has a skill S_{i}, age A_{i}, lower limit L_{i} and upper limit U_{i}. A person i can combine his skill with another person j if and only if age of another person A_{j} lies in range[L_{i}, U_{i}], i.e., A_{j} ≥ L_{i} and A_{j} ≤ R_{i} . Let's say that the set of id's of people with whom i^{th} individual can combine his skill is P, then STRENGTH(i) is defined as: where T denotes a non empty subset of P.
 G(T) denotes sum of skills of all index in T.
 F(0) = 1, F(1) = 8, F(2) = 10.
Since answer can be large, find STRENGTH(i)%(10^{6} + 3) for every i from 1 to N.
Input
 The first line of input contains a single integer N denoting the number of people.
 Each of the next N lines contains 4 spaceseparated integers S_{i}, A_{i}, L_{i}, U_{i} denoting the skill, age, lower limit and upper limit of i^{th} person.
Output
Output strength of each individual separated by space.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ A_{i}, L_{i},U_{i} ≤ 10^{9}
 1 ≤ S_{i} ≤ 10^{18}
Example
Input: 4 1 1 1 3 3 2 5 8 1 3 1 1 3 4 4 4 Output: 31417 0 10 0
Explanation
 i = 1 :
 S_{1} = 1
 P = {2, 3}
 All non empty subsets of P = {{2}, {3}, {2, 3}}
 for T = {2}, G(T) = S_{2} = 3, F(3 + 1) = F(4) =2915885705
 for T = {3}, G(T) = S_{3} = 1, F(1 + 1) = F(2) = 10
 for T = {2, 3}, G(T) = S_{2} + S_{3} = 4, F(4 + 1) = F(5) = 5730276345227
 Strength(1) = F(4) + F(2) + F(5) = 5733192230942
 Strength(1)%(10^{6} + 3) = 31417
 i = 2 :
 S_{2} = 3
 P = {}
 There are no empty subsets of P.
 Strength(2) = 0
 Strength(2)%(10^{6} + 3) = 0
 i = 3 :
 S_{3} = 1
 P = {1}
 All non empty subsets of P = {{1}}
 for T = {1}, G(T) = S_{1} = 1, F(1 + 1) = F(2) =10
 Strength(3) = F(2)= 10
 Strength(1)%(10^{6} + 3) = 10
 i = 4 :
 S_{4} = 3
 P = {}
 There are no empty subsets of P.
 Strength(4) = 0
 Strength(4)%(10^{6} + 3) = 0
Author:  blake_786 
Tags  blake_786 
Date Added:  7032018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions