College of Business and Finance
Postgraduate Council
MBA Program
MAGT 558 Research Methodology
First Semester, 2023/2024
Prof. Allam Hamdan
Research Case Study: SPSS Data Analysis and Interpretation
“The Impact of Embedding Artificial Intelligence on Human Resources Systems to Engage Employees in
Bahraini Companies”
Introduction:
Employee engagement refers to the emotional and intellectual commitment employees have towards
their work and organization. Engaged employees are motivated, dedicated, and passionate about their
roles, leading to higher productivity, job satisfaction, and organizational performance. Theoretical models
such as the Job Demands-Resources (JD-R) model, the Engagement-Performance Model, and the Social
Exchange Theory provide insights into the factors influencing employee engagement.
Artificial intelligence encompasses technologies that simulate human intelligence, enabling machines to
perform tasks that typically require human cognitive abilities, such as learning, problem-solving, and
decision-making. AI has the potential to revolutionize HR systems by automating routine tasks, enhancing
data analysis capabilities, and facilitating personalized employee experiences. Theoretical frameworks like
the Technology Acceptance Model (TAM) and the Unified Theory of Acceptance and Use of Technology
(UTAUT) shed light on the factors influencing AI adoption and its impact on organizational processes.
Integration of AI in HR Systems
The integration of AI in HR systems involves leveraging AI technologies to streamline HR processes,
improve decision-making, and enhance employee experiences. AI can be utilized for various HR functions,
including recruitment and selection, performance management, learning and development, employee
engagement, and talent analytics. Theoretical frameworks such as the Resource-Based View (RBV) and the
Human Capital Theory provide insights into the strategic implications of AI integration in HR systems.
The impact of AI integration on employee engagement is a complex and multifaceted phenomenon. AI can
positively influence employee engagement by providing personalized learning opportunities, facilitating
efficient communication, enabling data-driven decision-making, and reducing administrative burdens.
However, concerns regarding job security, ethical implications, and the human touch in HR processes need
to be considered. The Job Characteristics Model, the Social Information Processing Theory, and the
1
Psychological Contract Theory offer theoretical lenses to understand the mechanisms through which AI
can impact employee engagement.
When examining the impact of AI on employee engagement in Bahraini companies, it is crucial to consider
cultural and contextual factors. Bahraini culture values interpersonal relationships, teamwork, and
individual well-being. Theoretical frameworks like Hofstede’s Cultural Dimensions and the HighPerformance Work Systems (HPWS) provide insights into how cultural and contextual factors influence the
implementation and effectiveness of AI in HR systems.
The Assignment:
In this assignment, you will analyze the data collected from the Survey with 484 observations. The survey
focused on measuring the impact of embedding artificial intelligence (AI) in HR systems on employee
engagement in Bahraini companies.
The Survey link is:
https://docs.google.com/forms/d/e/1FAIpQLSfo4Rp7jloGGJI9PMB_qpPZLQLvh2iUSmbaK4uSdUmC7mL9
qw/viewform
Study Variables:
The variable
The dependent variables are:
Employee Performance Related Rewards
Decision Making
Communication
Work Life Balance
Leadership
The independent variable:
Artificial Intelligence
Code in
excel file
R
DM
C
WL
L
AI
You will use the provided data file, “Data MBA Case Study,” and the statistical software SPSS to perform
various statistical analyses and answer the following questions:
1) What are the basic stages that the statistical analysis of the thesis must go through?
2) Using the data file and SPSS, perform the following statistical analyses:
a) Test the validity of the data for statistical analysis using Cronbach’s alpha test. Prepare the
appropriate table and comment on the results.
b) Conduct descriptive statistical analysis of the demographic study variables and the basic study
variables. Prepare appropriate tables and comment on the findings.
c) The study hypotheses have been defined, focusing on the impact of embedding AI on various
aspects of employee engagement as follows:
2
Main Hypothesis: There is an impact of embedding artificial intelligence on HR systems in enhancing
employee engagement in public and private sector companies in Bahrain.
Five sub hypotheses have also been defined with each one of them focusing on a driver of employee
engagement that were mentioned earlier. This allowed ease of measuring the hypothesis at each variable
level:
H1: There is an impact of embedding artificial intelligence on employee Performance Related Rewards.
H2: There is an impact of embedding artificial intelligence on decision making.
H3: There is an impact of embedding artificial intelligence on communication.
H4: There is an impact of embedding artificial intelligence on employee work-life balance.
H5: There is an impact of embedding artificial intelligence on leadership.
Suggest an appropriate mathematical model for the relationship between the independent variable
(embedding AI) and each dependent variable.
d) Perform hypothesis tests using the appropriate statistical tests for each sub-hypothesis.
Interpret the results and discuss whether the hypotheses are accepted or rejected.
e) Explain the meaning of the terms: R, R2, and Adjusted R2.
f) Write an abstract for this research, providing a concise summary of the study and its key
results, in 150 words.
g) Write a final conclusion for this research, summarizing the key findings and implications, in
250 words.
Note:
–
Refer to the provided data file, “Data MBA Case Study,” and use SPSS for the statistical analysis.
Prepare tables, charts, and graphs where necessary to support your analysis.
Ensure your responses are clear, concise, and well-structured. Cite any relevant sources and
adhere to the given word limits.
Submission:
Submit your completed assignment as a document file (e.g., Word, PDF) by the deadline December 20,
2023, using the Moodle platform. Include the statistical analysis, tables, and any supporting visualizations
in your submission.
3
Gender
Age
1
2
1
1
2
1
2
1
1
1
2
1
1
1
1
2
2
1
2
1
1
1
2
2
1
2
2
1
1
1
2
1
1
1
1
2
1
2
1
1
2
1
1
2
1
1
2
2
4
4
2
5
3
4
2
2
1
5
3
4
3
2
3
3
4
2
3
4
2
3
5
5
5
4
4
4
2
3
3
3
3
5
3
3
5
5
2
4
4
3
5
3
Experience Education Industry AI1
2
3
6
3
3
2
5
4
6
5
4
6
3
3
1
4
3
4
4
3
3
4
3
3
3
3
6
3
3
6
1
3
6
5
4
4
4
4
4
5
3
7
2
3
6
4
3
4
4
4
6
4
4
4
5
4
1
3
3
4
4
3
8
4
4
6
3
3
1
5
5
1
5
4
6
5
3
4
5
4
1
4
4
1
5
4
3
4
4
4
3
3
1
5
3
1
3
3
6
4
3
6
4
3
4
5
4
1
4
4
4
4
3
4
5
5
3
5
4
6
4
4
8
5
3
4
5
4
4
4
3
4
5
4
8
4
4
1
AI2
2
1
2
2
2
2
2
2
2
1
1
5
2
1
1
4
2
1
2
2
1
2
1
2
1
2
2
2
2
2
5
2
1
2
2
1
3
2
2
5
2
2
4
2
4
2
AI3
3
2
2
1
1
2
4
3
2
1
1
3
3
2
3
4
3
1
2
3
1
3
3
3
1
3
2
5
2
2
5
4
1
3
3
1
5
2
3
5
3
3
5
3
3
2
AI4
3
3
2
4
1
2
3
3
2
1
1
3
3
3
2
4
3
2
2
2
1
3
2
3
2
3
1
3
1
2
5
3
1
3
1
1
3
2
4
4
3
2
4
2
3
2
4
2
3
4
2
3
3
4
3
1
1
4
3
3
5
2
3
3
3
3
4
3
2
3
2
3
4
4
4
2
5
3
2
3
3
4
5
3
4
5
3
4
4
4
4
3
2
2
1
2
1
2
1
2
2
1
1
1
2
2
1
2
1
2
2
2
4
2
5
4
1
4
1
5
5
2
2
2
2
3
5
3
4
4
3
4
4
5
3
2
5
2
5
5
4
3
4
2
4
5
5
4
5
3
4
3
2
3
3
4
4
3
4
3
3
3
3
3
3
4
4
4
8
6
6
4
6
3
4
1
2
6
6
4
4
1
4
8
4
4
6
1
2
2
2
2
2
3
2
2
1
2
2
2
2
2
2
4
1
1
2
2
3
1
2
2
4
5
5
3
2
4
3
2
4
3
4
2
2
1
2
3
1
2
2
4
5
5
3
3
5
4
3
3
3
4
2
2
4
3
4
4
4
3
4
5
5
5
4
5
4
4
5
4
5
2
3
1
1
1
1
1
2
2
1
2
2
1
1
2
2
1
1
1
1
2
1
2
1
1
1
2
1
1
5
3
2
5
5
5
2
4
2
3
3
4
2
5
2
4
5
4
3
4
2
4
4
3
4
4
4
5
4
3
5
5
5
3
5
3
4
4
4
3
5
3
5
5
4
4
5
3
5
5
4
5
5
4
3
5
4
3
3
5
3
2
4
4
4
4
3
4
4
4
5
3
3
4
3
4
3
3
3
4
5
6
3
6
6
6
1
4
6
4
4
8
4
4
1
1
3
2
4
6
2
1
6
4
6
1
4
4
1
4
5
3
5
3
2
3
2
2
1
3
2
2
2
4
4
5
2
2
2
4
3
2
2
2
5
2
2
3
2
2
3
3
4
3
3
3
3
2
2
4
4
4
5
1
3
3
3
3
4
3
3
4
3
2
4
3
3
4
3
4
2
2
2
3
1
1
3
4
4
5
1
3
3
4
3
5
2
3
4
3
4
4
3
4
3
4
4
3
4
3
4
4
3
5
4
4
5
4
3
4
4
4
5
4
3
4
1
2
2
2
2
2
1
2
1
1
1
1
1
2
1
1
2
2
2
1
1
1
1
2
1
2
2
1
1
1
2
1
1
2
1
2
1
1
1
2
1
1
1
1
2
2
1
4
3
4
2
2
4
4
5
4
3
3
5
3
4
4
5
4
5
3
4
4
5
5
1
5
2
4
3
5
2
2
4
4
2
5
3
4
2
2
1
5
3
4
3
2
3
3
5
4
4
3
3
5
5
5
5
4
4
5
4
5
5
5
5
5
4
5
5
5
5
1
5
4
4
4
5
2
3
5
5
3
4
4
4
3
3
1
5
4
5
2
4
4
4
3
4
4
4
4
4
4
3
4
3
3
4
4
5
3
3
4
3
3
3
3
3
4
3
5
4
4
4
5
3
3
4
4
3
3
3
3
3
3
3
4
4
3
3
3
4
4
3
6
1
4
6
1
4
3
3
4
4
1
6
2
1
6
6
1
1
8
1
4
6
4
3
6
4
6
3
6
2
6
6
1
4
3
3
6
6
6
4
4
7
6
4
6
4
2
3
2
2
3
2
2
2
4
2
1
2
2
2
2
2
5
2
2
2
1
3
2
1
1
1
2
2
4
2
1
2
2
2
2
2
2
2
1
1
5
2
1
1
4
2
1
2
3
2
3
3
2
3
3
3
2
1
3
4
3
3
3
3
3
2
2
2
3
3
1
1
3
3
3
5
3
2
2
1
1
2
4
3
2
1
1
3
3
2
3
4
3
1
4
3
3
3
2
2
4
3
4
2
2
3
4
2
3
4
2
4
4
2
1
3
3
4
2
3
1
4
4
3
3
2
4
1
2
3
3
2
1
1
3
3
3
2
4
3
2
4
3
3
4
3
4
4
4
4
4
2
5
4
2
4
4
2
4
4
3
4
3
4
4
4
3
3
5
5
4
2
3
4
2
3
3
4
3
1
1
4
3
3
5
2
3
3
2
1
1
1
2
2
1
2
2
1
1
1
2
1
1
1
1
2
1
2
1
1
2
1
1
2
1
1
2
2
1
2
1
2
1
2
2
1
1
1
2
2
1
2
1
2
2
4
2
3
4
2
3
5
5
5
4
4
4
2
3
3
3
3
5
3
3
5
5
2
4
4
3
5
3
2
4
2
5
4
1
4
1
5
5
2
2
2
2
3
5
3
4
4
5
3
4
4
3
5
5
5
5
4
5
4
3
5
3
4
4
5
4
4
5
5
4
5
5
4
5
4
3
4
4
5
3
2
5
2
5
5
4
3
4
2
4
5
5
4
5
4
3
3
4
3
5
4
3
4
4
4
4
3
3
3
3
3
4
4
3
5
4
4
3
4
3
4
4
3
4
3
2
3
3
4
4
3
4
3
3
3
3
3
3
4
4
4
1
4
8
6
1
1
6
4
1
1
3
4
1
1
6
6
4
1
4
4
3
6
8
4
4
4
8
1
8
6
6
4
6
3
4
1
2
6
6
4
4
1
4
8
4
4
6
2
2
1
2
1
2
1
2
2
2
2
2
5
2
1
2
2
1
3
2
2
5
2
2
4
2
4
2
1
2
2
2
2
2
3
2
2
1
2
2
2
2
2
2
4
1
1
2
3
1
3
3
3
1
3
2
5
2
2
5
4
1
3
3
1
5
2
3
5
3
3
5
3
3
2
2
2
3
1
2
2
4
5
5
3
2
4
3
2
4
3
4
2
2
2
2
1
3
2
3
2
3
1
3
1
2
5
3
1
3
1
1
3
2
4
4
3
2
4
2
3
2
1
2
3
1
2
2
4
5
5
3
3
5
4
3
3
3
4
2
2
3
3
4
3
2
3
2
3
4
4
4
2
5
3
2
3
3
4
5
3
4
5
3
4
4
4
4
3
4
3
4
4
4
3
4
5
5
5
4
5
4
4
5
4
5
2
3
1
1
1
1
1
2
2
1
2
2
1
1
2
2
1
1
1
1
2
1
2
1
1
1
2
1
1
1
2
2
2
2
2
1
2
1
1
1
1
1
2
1
1
2
2
2
1
5
3
2
5
5
5
2
4
2
3
3
4
2
5
2
4
5
4
3
4
2
4
4
3
4
4
4
4
3
4
2
2
4
4
5
4
3
3
5
3
4
4
5
4
5
3
4
5
4
3
5
5
5
3
5
3
4
4
4
3
5
3
5
5
4
4
5
3
5
5
4
5
5
4
5
4
4
3
3
5
5
5
5
4
4
5
4
5
5
5
5
5
4
5
3
5
4
3
3
5
3
2
4
4
4
4
3
4
4
4
5
3
3
4
3
4
3
3
3
4
5
3
4
4
4
4
4
4
3
4
3
3
4
4
5
3
3
4
3
3
3
6
3
6
6
6
1
4
6
4
4
8
4
4
1
1
3
2
4
6
2
1
6
4
6
1
4
4
3
6
1
4
6
1
4
3
3
4
4
1
6
2
1
6
6
1
1
8
1
4
5
3
5
3
2
3
2
2
1
3
2
2
2
4
4
5
2
2
2
4
3
2
2
2
5
2
3
2
2
3
2
2
2
4
2
1
2
2
2
2
2
5
2
2
2
2
2
3
2
2
3
3
4
3
3
3
3
2
2
4
4
4
5
1
3
3
3
3
4
3
3
4
2
3
2
3
3
2
3
3
3
2
1
3
4
3
3
3
3
3
2
2
3
2
4
3
3
4
3
4
2
2
2
3
1
1
3
4
4
5
1
3
3
4
3
5
2
3
4
4
3
3
3
2
2
4
3
4
2
2
3
4
2
3
4
2
4
4
2
3
4
4
3
4
3
4
4
3
4
3
4
4
3
5
4
4
5
4
3
4
4
4
5
4
3
4
4
3
3
4
3
4
4
4
4
4
2
5
4
2
4
4
2
4
4
3
1
1
1
2
1
2
2
1
1
1
2
1
1
2
1
2
1
1
1
2
1
1
1
1
2
2
1
2
1
1
1
2
2
1
2
2
1
1
1
2
1
1
1
1
2
1
2
4
5
5
1
5
2
4
3
5
2
2
4
4
2
5
3
4
2
2
1
5
3
4
3
2
3
3
4
2
3
4
2
3
5
5
5
4
4
4
2
3
3
3
3
5
3
3
5
5
5
1
5
4
4
4
5
2
3
5
5
3
4
4
4
3
3
1
5
4
5
2
4
4
4
5
3
4
4
3
5
5
5
5
4
5
4
3
5
3
4
4
5
4
4
3
3
4
3
5
4
4
4
5
3
3
4
4
3
3
3
3
3
3
3
4
4
3
3
3
4
4
4
3
3
4
3
5
4
3
4
4
4
4
3
3
3
3
3
4
4
3
1
4
6
4
3
6
4
6
3
6
2
6
6
1
4
3
3
6
6
6
4
4
7
6
4
6
4
1
4
8
6
1
1
6
4
1
1
3
4
1
1
6
6
4
1
4
4
1
3
2
1
1
1
2
2
4
2
1
2
2
2
2
2
2
2
1
1
5
2
1
1
4
2
1
2
2
1
2
1
2
1
2
2
2
2
2
5
2
1
2
2
1
3
2
2
3
3
1
1
3
3
3
5
3
2
2
1
1
2
4
3
2
1
1
3
3
2
3
4
3
1
2
3
1
3
3
3
1
3
2
5
2
2
5
4
1
3
3
1
5
2
1
3
3
4
2
3
1
4
4
3
3
2
4
1
2
3
3
2
1
1
3
3
3
2
4
3
2
2
2
1
3
2
3
2
3
1
3
1
2
5
3
1
3
1
1
3
2
4
3
4
4
4
3
3
5
5
4
2
3
4
2
3
3
4
3
1
1
4
3
3
5
2
3
3
3
3
4
3
2
3
2
3
4
4
4
2
5
3
2
3
3
4
5
3
1
1
2
1
1
2
1
1
2
2
1
2
1
2
1
2
2
1
1
1
2
2
1
2
1
2
2
1
1
1
1
1
2
2
1
2
2
1
1
2
2
1
1
1
1
2
1
5
5
2
4
4
3
5
3
2
4
2
5
4
1
4
1
5
5
2
2
2
2
3
5
3
4
4
5
3
2
5
5
5
2
4
2
3
3
4
2
5
2
4
5
4
3
4
5
5
4
5
5
4
5
4
3
4
4
5
3
2
5
2
5
5
4
3
4
2
4
5
5
4
5
5
4
3
5
5
5
3
5
3
4
4
4
3
5
3
5
5
4
4
5
5
4
4
3
4
3
4
4
3
4
3
2
3
3
4
4
3
4
3
3
3
3
3
3
4
4
4
3
5
4
3
3
5
3
2
4
4
4
4
3
4
4
4
5
3
3
4
3
6
8
4
4
4
8
1
8
6
6
4
6
3
4
1
2
6
6
4
4
1
4
8
4
4
6
6
3
6
6
6
1
4
6
4
4
8
4
4
1
1
3
2
4
6
2
2
5
2
2
4
2
4
2
1
2
2
2
2
2
3
2
2
1
2
2
2
2
2
2
4
1
1
1
4
5
3
5
3
2
3
2
2
1
3
2
2
2
4
4
5
2
2
3
5
3
3
5
3
3
2
2
2
3
1
2
2
4
5
5
3
2
4
3
2
4
3
4
2
2
2
2
3
2
2
3
3
4
3
3
3
3
2
2
4
4
4
5
1
3
4
4
3
2
4
2
3
2
1
2
3
1
2
2
4
5
5
3
3
5
4
3
3
3
4
2
2
3
2
4
3
3
4
3
4
2
2
2
3
1
1
3
4
4
5
1
3
4
5
3
4
4
4
4
3
4
3
4
4
4
3
4
5
5
5
4
5
4
4
5
4
5
2
3
3
4
4
3
4
3
4
4
3
4
3
4
4
3
5
4
4
5
4
3
2
1
1
1
2
1
1
1
2
2
2
2
2
1
2
1
1
1
1
1
2
1
1
2
2
2
1
1
1
1
2
1
2
2
1
1
1
2
1
1
2
1
2
1
1
1
2
2
4
4
3
4
4
4
4
3
4
2
2
4
4
5
4
3
3
5
3
4
4
5
4
5
3
4
4
5
5
1
5
2
4
3
5
2
2
4
4
2
5
3
4
2
2
1
3
5
5
4
5
5
4
5
4
4
3
3
5
5
5
5
4
4
5
4
5
5
5
5
5
4
5
5
5
5
1
5
4
4
4
5
2
3
5
5
3
4
4
4
3
3
1
3
4
3
3
3
4
5
3
4
4
4
4
4
4
3
4
3
3
4
4
5
3
3
4
3
3
3
3
3
4
3
5
4
4
4
5
3
3
4
4
3
3
3
3
3
3
3
1
6
4
6
1
4
4
3
6
1
4
6
1
4
3
3
4
4
1
6
2
1
6
6
1
1
8
1
4
6
4
3
6
4
6
3
6
2
6
6
1
4
3
3
6
6
6
2
4
3
2
2
2
5
2
3
2
2
3
2
2
2
4
2
1
2
2
2
2
2
5
2
2
2
1
3
2
1
1
1
2
2
4
2
1
2
2
2
2
2
2
2
1
1
3
3
3
4
3
3
4
2
3
2
3
3
2
3
3
3
2
1
3
4
3
3
3
3
3
2
2
2
3
3
1
1
3
3
3
5
3
2
2
1
1
2
4
3
2
1
1
3
4
3
5
2
3
4
4
3
3
3
2
2
4
3
4
2
2
3
4
2
3
4
2
4
4
2
1
3
3
4
2
3
1
4
4
3
3
2
4
1
2
3
3
2
1
1
4
4
4
5
4
3
4
4
3
3
4
3
4
4
4
4
4
2
5
4
2
4
4
2
4
4
3
4
3
4
4
4
3
3
5
5
4
2
3
4
2
3
3
4
3
1
1
1
1
1
1
2
2
1
2
1
1
1
2
2
1
2
2
1
1
1
2
1
1
1
1
2
1
2
1
1
2
1
1
2
1
1
2
2
1
2
1
2
1
2
2
1
1
1
5
3
4
3
2
3
3
4
2
3
4
2
3
5
5
5
4
4
4
2
3
3
3
3
5
3
3
5
5
2
4
4
3
5
3
2
4
2
5
4
1
4
1
5
5
2
2
5
4
5
2
4
4
4
5
3
4
4
3
5
5
5
5
4
5
4
3
5
3
4
4
5
4
4
5
5
4
5
5
4
5
4
3
4
4
5
3
2
5
2
5
5
4
3
4
4
3
3
3
4
4
4
3
3
4
3
5
4
3
4
4
4
4
3
3
3
3
3
4
4
3
5
4
4
3
4
3
4
4
3
4
3
2
3
3
4
4
3
4
3
3
4
4
7
6
4
6
4
1
4
8
6
1
1
6
4
1
1
3
4
1
1
6
6
4
1
4
4
3
6
8
4
4
4
8
1
8
6
6
4
6
3
4
1
2
6
6
4
5
2
1
1
4
2
1
2
2
1
2
1
2
1
2
2
2
2
2
5
2
1
2
2
1
3
2
2
5
2
2
4
2
4
2
1
2
2
2
2
2
3
2
2
1
2
2
3
3
2
3
4
3
1
2
3
1
3
3
3
1
3
2
5
2
2
5
4
1
3
3
1
5
2
3
5
3
3
5
3
3
2
2
2
3
1
2
2
4
5
5
3
2
4
3
3
3
2
4
3
2
2
2
1
3
2
3
2
3
1
3
1
2
5
3
1
3
1
1
3
2
4
4
3
2
4
2
3
2
1
2
3
1
2
2
4
5
5
3
3
5
4
3
3
5
2
3
3
3
3
4
3
2
3
2
3
4
4
4
2
5
3
2
3
3
4
5
3
4
5
3
4
4
4
4
3
4
3
4
4
4
3
4
5
5
5
4
5
2
2
1
2
1
2
2
1
1
1
1
1
2
2
1
2
2
1
1
2
2
1
1
1
1
2
1
2
1
1
1
2
1
1
1
2
2
2
2
2
1
2
1
1
1
1
1
2
2
3
5
3
4
4
5
3
2
5
5
5
2
4
2
3
3
4
2
5
2
4
5
4
3
4
2
4
4
3
4
4
4
4
3
4
2
2
4
4
5
4
3
3
5
3
4
2
4
5
5
4
5
5
4
3
5
5
5
3
5
3
4
4
4
3
5
3
5
5
4
4
5
3
5
5
4
5
5
4
5
4
4
3
3
5
5
5
5
4
4
5
4
3
3
3
3
4
4
4
3
5
4
3
3
5
3
2
4
4
4
4
3
4
4
4
5
3
3
4
3
4
3
3
3
4
5
3
4
4
4
4
4
4
3
4
3
3
4
4
4
1
4
8
4
4
6
6
3
6
6
6
1
4
6
4
4
8
4
4
1
1
3
2
4
6
2
1
6
4
6
1
4
4
3
6
1
4
6
1
4
3
3
4
4
1
6
2
2
2
2
4
1
1
1
4
5
3
5
3
2
3
2
2
1
3
2
2
2
4
4
5
2
2
2
4
3
2
2
2
5
2
3
2
2
3
2
2
2
4
2
1
2
2
3
2
4
3
4
2
2
2
2
3
2
2
3
3
4
3
3
3
3
2
2
4
4
4
5
1
3
3
3
3
4
3
3
4
2
3
2
3
3
2
3
3
3
2
1
3
4
4
3
3
3
4
2
2
3
2
4
3
3
4
3
4
2
2
2
3
1
1
3
4
4
5
1
3
3
4
3
5
2
3
4
4
3
3
3
2
2
4
3
4
2
2
3
4
4
4
5
4
5
2
3
3
4
4
3
4
3
4
4
3
4
3
4
4
3
5
4
4
5
4
3
4
4
4
5
4
3
4
4
3
3
4
3
4
4
4
4
4
2
5
4
2
1
1
2
2
2
1
1
1
1
2
1
2
2
1
1
4
4
5
4
5
3
4
4
5
5
1
5
2
4
3
5
5
5
5
5
5
4
5
5
5
5
1
5
4
4
4
5
5
3
3
4
3
3
3
3
3
4
3
5
4
4
4
5
2
1
6
6
1
1
8
1
4
6
4
3
6
4
6
3
2
2
2
5
2
2
2
1
3
2
1
1
1
2
2
4
3
3
3
3
3
2
2
2
3
3
1
1
3
3
3
5
2
3
4
2
4
4
2
1
3
3
4
2
3
1
4
4
2
4
4
2
4
4
3
4
3
4
4
4
3
3
5
5
R1
R2
4
4
3
4
1
4
2
3
2
1
1
1
1
2
4
3
2
2
1
3
3
2
3
3
1
2
3
3
3
3
5
4
4
1
3
1
5
1
4
4
3
4
4
2
4
2
R3
4
4
2
4
1
3
3
2
1
1
1
3
2
3
3
3
5
3
2
3
3
3
3
2
1
3
2
3
2
3
4
3
4
1
4
1
4
4
3
4
3
4
4
2
4
2
R4
1
3
2
1
1
2
2
2
1
1
1
2
1
2
3
2
1
3
3
2
2
3
3
3
1
3
1
3
1
2
2
4
1
3
1
1
4
1
4
4
4
2
4
1
4
3
R5
2
2
3
4
1
3
4
4
1
1
1
3
2
3
3
3
3
3
2
3
3
3
3
3
1
3
3
3
2
2
4
3
4
3
2
1
5
3
4
4
3
3
4
2
3
4
DM1
2
2
3
4
4
2
3
2
1
1
1
4
3
3
3
3
3
3
3
3
3
3
3
3
1
2
3
4
4
2
3
3
1
3
1
4
4
3
4
4
3
3
5
4
4
3
DM2
4
4
4
4
1
3
3
2
1
1
1
4
2
4
3
4
5
3
3
3
3
3
3
3
3
3
2
4
3
3
4
4
3
3
4
3
4
3
4
5
3
5
4
3
4
3
DM3
4
3
3
4
1
3
2
2
1
1
1
4
2
3
3
4
4
3
2
3
3
3
3
3
3
3
2
3
2
3
4
4
2
3
3
2
5
3
5
4
3
3
4
3
4
4
DM4
5
5
2
5
1
5
1
3
1
1
1
3
2
3
3
3
5
3
3
3
3
3
3
3
3
3
2
5
2
2
4
3
1
5
5
2
4
3
5
5
3
3
5
5
5
3
4
3
1
4
1
2
2
4
1
1
1
3
2
3
3
3
4
2
2
3
3
3
3
3
3
3
2
3
2
3
4
4
2
3
4
2
4
3
4
4
3
3
4
2
4
4
4
3
3
4
4
4
4
5
5
4
4
4
4
4
1
4
5
3
2
5
4
5
4
4
4
5
5
5
4
5
5
4
4
4
4
5
3
3
4
5
1
1
4
1
4
5
5
4
3
4
4
3
4
4
2
1
3
4
5
3
3
3
5
4
1
5
4
5
4
4
3
5
4
4
3
2
4
3
3
2
4
3
3
5
5
4
4
4
4
4
4
5
4
3
3
5
4
5
3
5
4
5
5
5
5
4
5
4
4
4
5
4
3
4
5
4
5
4
4
5
5
5
5
5
5
5
4
4
4
4
4
3
3
5
5
5
2
2
3
5
4
4
4
4
5
5
4
4
5
4
3
3
5
5
5
4
2
5
4
5
5
5
4
4
4
4
5
4
5
3
3
2
2
4
3
2
2
4
4
3
4
4
4
1
2
2
3
5
4
4
3
1
3
4
2
2
3
2
1
3
4
4
4
3
4
3
4
4
2
3
4
3
3
2
5
5
4
4
3
4
4
4
4
4
4
2
3
4
2
3
2
3
2
2
3
3
2
1
4
4
2
4
4
2
2
1
4
4
2
1
4
2
1
3
3
4
2
3
3
4
4
4
1
3
4
4
4
2
4
4
4
2
4
4
3
5
3
4
3
2
3
3
3
4
4
3
3
3
4
3
3
3
4
4
3
4
3
4
3
3
3
4
5
3
3
4
2
4
4
4
4
4
3
3
4
4
5
3
4
4
4
4
5
5
4
4
4
4
4
4
4
4
4
2
3
3
3
4
3
3
4
4
4
4
3
4
4
5
3
4
4
4
4
3
3
4
4
4
4
4
2
3
3
5
5
5
3
3
5
5
5
5
3
5
5
3
5
5
4
3
5
3
5
5
5
5
3
2
2
3
3
4
4
3
3
4
4
4
3
4
3
4
3
3
4
4
3
3
3
4
4
4
3
4
1
2
1
2
4
3
4
4
4
3
3
4
4
4
4
3
2
4
3
4
4
4
4
5
4
2
2
4
4
4
4
3
4
1
4
2
3
2
1
1
1
1
2
4
3
2
2
4
4
3
3
4
4
5
4
4
4
4
4
4
4
4
4
2
4
3
5
4
4
4
4
4
4
4
4
4
4
4
2
4
1
3
3
2
1
1
1
3
2
3
3
3
5
3
1
4
1
1
2
1
2
2
2
4
1
1
1
4
4
1
3
4
2
4
2
4
4
2
4
1
3
1
2
1
3
2
1
1
2
2
2
1
1
1
2
1
2
3
2
1
3
4
4
3
2
4
4
5
3
3
4
3
4
4
4
4
4
2
5
4
4
4
4
4
3
3
4
4
4
4
2
2
3
4
1
3
4
4
1
1
1
3
2
3
3
3
3
3
3
4
3
3
4
3
3
3
3
3
4
4
4
4
4
4
2
4
3
4
4
3
4
4
3
3
3
4
4
2
2
3
4
4
2
3
2
1
1
1
4
3
3
3
3
3
3
4
4
5
4
4
3
4
4
4
4
4
4
4
4
4
3
5
5
4
4
5
4
4
3
5
5
5
5
5
4
4
4
4
1
3
3
2
1
1
1
4
2
4
3
4
5
3
4
4
4
2
4
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
3
5
5
4
3
3
4
1
3
2
2
1
1
1
4
2
3
3
4
4
3
5
5
5
2
5
3
5
5
5
5
5
5
5
5
5
5
5
4
5
5
5
4
5
5
4
3
3
5
5
5
5
2
5
1
5
1
3
1
1
1
3
2
3
3
3
5
3
4
4
4
2
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
4
4
4
4
4
5
3
3
5
5
4
3
1
4
1
2
2
4
1
1
1
3
2
3
3
3
4
2
1
3
3
2
3
3
1
2
3
3
3
3
5
4
4
1
3
1
5
1
4
4
3
4
4
2
4
2
4
3
3
4
4
4
4
5
5
4
4
4
4
4
1
4
5
3
2
2
3
3
3
3
2
1
3
2
3
2
3
4
3
4
1
4
1
4
4
3
4
3
4
4
2
4
2
5
4
5
4
4
4
5
5
5
4
5
5
4
4
4
4
5
3
3
3
2
2
3
3
3
1
3
1
3
1
2
2
4
1
3
1
1
4
1
4
4
4
2
4
1
4
3
4
5
1
1
4
1
4
5
5
4
3
4
4
3
4
4
2
1
3
2
3
3
3
3
3
1
3
3
3
2
2
4
3
4
3
2
1
5
3
4
4
3
3
4
2
3
4
4
5
3
3
3
5
4
1
5
4
5
4
4
3
5
4
4
3
2
3
3
3
3
3
3
1
2
3
4
4
2
3
3
1
3
1
4
4
3
4
4
3
3
5
4
4
3
4
3
3
2
4
3
3
5
5
4
4
4
4
4
4
5
4
3
3
3
3
3
3
3
3
3
3
2
4
3
3
4
4
3
3
4
3
4
3
4
5
3
5
4
3
4
3
5
4
5
3
5
4
5
5
5
5
4
5
4
4
4
5
4
3
4
2
3
3
3
3
3
3
3
2
3
2
3
4
4
2
3
3
2
5
3
5
4
3
3
4
3
4
4
5
4
5
4
4
5
5
5
5
5
5
5
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
2
5
2
2
4
3
1
5
5
2
4
3
5
5
3
3
5
5
5
3
5
5
5
2
2
3
5
4
4
4
4
5
5
4
4
5
4
3
3
2
3
3
3
3
3
3
3
2
3
2
3
4
4
2
3
4
2
4
3
4
4
3
3
4
2
4
4
5
5
5
4
2
5
4
5
5
5
4
4
4
4
5
4
5
3
3
2
2
4
3
2
2
4
4
3
4
4
4
1
2
2
3
5
4
4
3
1
3
4
2
2
3
2
1
2
1
2
4
3
4
4
4
3
3
4
4
4
4
3
2
4
3
4
1
3
4
4
4
3
4
3
4
4
2
3
4
3
3
2
5
5
4
4
3
4
4
4
4
4
4
4
4
3
3
4
4
5
4
4
4
4
4
4
4
4
4
2
4
3
5
2
3
4
2
3
2
3
2
2
3
3
2
1
4
4
2
4
4
2
2
1
4
4
2
1
4
2
1
4
1
1
2
1
2
2
2
4
1
1
1
4
4
1
3
4
2
4
1
3
3
4
2
3
3
4
4
4
1
3
4
4
4
2
4
4
4
2
4
4
3
5
3
4
3
4
4
3
2
4
4
5
3
3
4
3
4
4
4
4
4
2
5
4
4
2
3
3
3
4
4
3
3
3
4
3
3
3
4
4
3
4
3
4
3
3
3
4
5
3
3
4
3
4
3
3
4
3
3
3
3
3
4
4
4
4
4
4
2
4
3
4
2
4
4
4
4
4
3
3
4
4
5
3
4
4
4
4
5
5
4
4
4
4
4
4
4
4
4
4
4
5
4
4
3
4
4
4
4
4
4
4
4
4
3
5
5
4
4
2
3
3
3
4
3
3
4
4
4
4
3
4
4
5
3
4
4
4
4
3
3
4
4
4
4
4
4
4
4
2
4
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
2
3
3
5
5
5
3
3
5
5
5
5
3
5
5
3
5
5
4
3
5
3
5
5
5
5
3
5
5
5
2
5
3
5
5
5
5
5
5
5
5
5
5
5
4
5
5
2
2
3
3
4
4
3
3
4
4
4
3
4
3
4
3
3
4
4
3
3
3
4
4
4
3
4
4
4
4
2
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
4
4
4
4
5
4
2
2
4
4
4
4
3
4
1
4
2
3
2
1
1
1
1
2
4
3
2
2
1
3
3
2
3
3
1
2
3
3
3
3
5
4
4
1
3
1
5
1
4
4
4
4
4
4
4
4
4
4
4
2
4
1
3
3
2
1
1
1
3
2
3
3
3
5
3
2
3
3
3
3
2
1
3
2
3
2
3
4
3
4
1
4
1
4
4
2
4
4
2
4
1
3
1
2
1
3
2
1
1
2
2
2
1
1
1
2
1
2
3
2
1
3
3
2
2
3
3
3
1
3
1
3
1
2
2
4
1
3
1
1
4
1
4
4
4
3
3
4
4
4
4
2
2
3
4
1
3
4
4
1
1
1
3
2
3
3
3
3
3
2
3
3
3
3
3
1
3
3
3
2
2
4
3
4
3
2
1
5
3
4
3
4
4
3
3
3
4
4
2
2
3
4
4
2
3
2
1
1
1
4
3
3
3
3
3
3
3
3
3
3
3
3
1
2
3
4
4
2
3
3
1
3
1
4
4
3
5
4
4
3
5
5
5
5
5
4
4
4
4
1
3
3
2
1
1
1
4
2
4
3
4
5
3
3
3
3
3
3
3
3
3
2
4
3
3
4
4
3
3
4
3
4
3
4
4
4
4
5
5
3
5
5
4
3
3
4
1
3
2
2
1
1
1
4
2
3
3
4
4
3
2
3
3
3
3
3
3
3
2
3
2
3
4
4
2
3
3
2
5
3
5
4
5
5
4
3
3
5
5
5
5
2
5
1
5
1
3
1
1
1
3
2
3
3
3
5
3
3
3
3
3
3
3
3
3
2
5
2
2
4
3
1
5
5
2
4
3
4
4
4
4
5
3
3
5
5
4
3
1
4
1
2
2
4
1
1
1
3
2
3
3
3
4
2
2
3
3
3
3
3
3
3
2
3
2
3
4
4
2
3
4
2
4
3
4
4
3
4
4
2
4
2
4
3
3
4
4
4
4
5
5
4
4
4
4
4
1
4
5
3
2
2
2
4
3
2
2
4
4
3
4
4
4
1
2
2
3
5
4
4
3
3
4
3
4
4
2
4
2
5
4
5
4
4
4
5
5
5
4
5
5
4
4
4
4
5
3
3
1
3
4
4
4
3
4
3
4
4
2
3
4
3
3
2
5
5
4
4
4
4
4
2
4
1
4
3
4
5
1
1
4
1
4
5
5
4
3
4
4
3
4
4
2
1
3
2
3
4
2
3
2
3
2
2
3
3
2
1
4
4
2
4
4
2
2
4
4
3
3
4
2
3
4
4
5
3
3
3
5
4
1
5
4
5
4
4
3
5
4
4
3
2
1
3
3
4
2
3
3
4
4
4
1
3
4
4
4
2
4
4
4
2
4
4
3
3
5
4
4
3
4
3
3
2
4
3
3
5
5
4
4
4
4
4
4
5
4
3
3
2
3
3
3
4
4
3
3
3
4
3
3
3
4
4
3
4
3
4
3
4
5
3
5
4
3
4
3
5
4
5
3
5
4
5
5
5
5
4
5
4
4
4
5
4
3
4
2
4
4
4
4
4
3
3
4
4
5
3
4
4
4
4
5
5
4
4
5
4
3
3
4
3
4
4
5
4
5
4
4
5
5
5
5
5
5
5
4
4
4
4
4
3
3
2
3
3
3
4
3
3
4
4
4
4
3
4
4
5
3
4
4
4
4
5
5
3
3
5
5
5
3
5
5
5
2
2
3
5
4
4
4
4
5
5
4
4
5
4
3
3
2
3
3
5
5
5
3
3
5
5
5
5
3
5
5
3
5
5
4
3
4
4
3
3
4
2
4
4
5
5
5
4
2
5
4
5
5
5
4
4
4
4
5
4
5
3
3
2
2
3
3
4
4
3
3
4
4
4
3
4
3
4
3
3
4
4
3
1
3
4
2
2
3
2
1
2
1
2
4
3
4
4
4
3
3
4
4
4
4
3
2
4
3
4
4
4
4
5
4
2
2
4
4
4
4
3
4
1
4
2
3
2
1
1
3
4
4
4
4
4
4
4
4
3
3
4
4
5
4
4
4
4
4
4
4
4
4
2
4
3
5
4
4
4
4
4
4
4
4
4
4
4
2
4
1
3
3
2
1
1
1
1
4
4
2
1
4
2
1
4
1
1
2
1
2
2
2
4
1
1
1
4
4
1
3
4
2
4
2
4
4
2
4
1
3
1
2
1
3
2
1
1
2
2
2
1
1
1
4
4
3
5
3
4
3
4
4
3
2
4
4
5
3
3
4
3
4
4
4
4
4
2
5
4
4
4
4
4
3
3
4
4
4
4
2
2
3
4
1
3
4
4
1
1
1
3
3
4
5
3
3
4
3
4
3
3
4
3
3
3
3
3
4
4
4
4
4
4
2
4
3
4
4
3
4
4
3
3
3
4
4
2
2
3
4
4
2
3
2
1
1
1
4
4
4
4
4
4
4
4
4
5
4
4
3
4
4
4
4
4
4
4
4
4
3
5
5
4
4
5
4
4
3
5
5
5
5
5
4
4
4
4
1
3
3
2
1
1
1
3
3
4
4
4
4
4
4
4
4
2
4
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
3
5
5
4
3
3
4
1
3
2
2
1
1
1
5
3
5
5
5
5
3
5
5
5
2
5
3
5
5
5
5
5
5
5
5
5
5
5
4
5
5
5
4
5
5
4
3
3
5
5
5
5
2
5
1
5
1
3
1
1
1
3
3
4
4
4
3
4
4
4
4
2
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
4
4
4
4
4
5
3
3
5
5
4
3
1
4
1
2
2
4
1
1
1
1
1
2
4
3
2
2
1
3
3
2
3
3
1
2
3
3
3
3
5
4
4
1
3
1
5
1
4
4
3
4
4
2
4
2
4
3
3
4
4
4
4
5
5
4
4
4
3
2
3
3
3
5
3
2
3
3
3
3
2
1
3
2
3
2
3
4
3
4
1
4
1
4
4
3
4
3
4
4
2
4
2
5
4
5
4
4
4
5
5
5
4
5
5
2
1
2
3
2
1
3
3
2
2
3
3
3
1
3
1
3
1
2
2
4
1
3
1
1
4
1
4
4
4
2
4
1
4
3
4
5
1
1
4
1
4
5
5
4
3
4
3
2
3
3
3
3
3
2
3
3
3
3
3
1
3
3
3
2
2
4
3
4
3
2
1
5
3
4
4
3
3
4
2
3
4
4
5
3
3
3
5
4
1
5
4
5
4
4
3
3
3
3
3
3
3
3
3
3
3
3
1
2
3
4
4
2
3
3
1
3
1
4
4
3
4
4
3
3
5
4
4
3
4
3
3
2
4
3
3
5
5
4
4
4
4
2
4
3
4
5
3
3
3
3
3
3
3
3
3
2
4
3
3
4
4
3
3
4
3
4
3
4
5
3
5
4
3
4
3
5
4
5
3
5
4
5
5
5
5
4
5
4
2
3
3
4
4
3
2
3
3
3
3
3
3
3
2
3
2
3
4
4
2
3
3
2
5
3
5
4
3
3
4
3
4
4
5
4
5
4
4
5
5
5
5
5
5
5
3
2
3
3
3
5
3
3
3
3
3
3
3
3
3
2
5
2
2
4
3
1
5
5
2
4
3
5
5
3
3
5
5
5
3
5
5
5
2
2
3
5
4
4
4
4
5
3
2
3
3
3
4
2
2
3
3
3
3
3
3
3
2
3
2
3
4
4
2
3
4
2
4
3
4
4
3
3
4
2
4
4
5
5
5
4
2
5
4
5
5
5
4
4
4
4
1
4
5
3
2
2
2
4
3
2
2
4
4
3
4
4
4
1
2
2
3
5
4
4
3
1
3
4
2
2
3
2
1
2
1
2
4
3
4
4
4
3
3
4
4
4
4
4
4
5
3
3
1
3
4
4
4
3
4
3
4
4
2
3
4
3
3
2
5
5
4
4
3
4
4
4
4
4
4
4
4
3
3
4
4
5
4
4
4
4
4
4
4
3
4
4
2
1
3
2
3
4
2
3
2
3
2
2
3
3
2
1
4
4
2
4
4
2
2
1
4
4
2
1
4
2
1
4
1
1
2
1
2
2
2
4
1
1
1
4
3
5
4
4
3
2
1
3
3
4
2
3
3
4
4
4
1
3
4
4
4
2
4
4
4
2
4
4
3
5
3
4
3
4
4
3
2
4
4
5
3
3
4
3
4
4
4
4
4
5
4
3
3
2
3
3
3
4
4
3
3
3
4
3
3
3
4
4
3
4
3
4
3
3
3
4
5
3
3
4
3
4
3
3
4
3
3
3
3
3
4
4
4
4
4
4
5
4
3
4
2
4
4
4
4
4
3
3
4
4
5
3
4
4
4
4
5
5
4
4
4
4
4
4
4
4
4
4
4
5
4
4
3
4
4
4
4
4
4
4
4
4
4
4
4
3
3
2
3
3
3
4
3
3
4
4
4
4
3
4
4
5
3
4
4
4
4
3
3
4
4
4
4
4
4
4
4
2
4
3
4
4
4
4
4
4
4
5
4
4
5
4
3
3
2
3
3
5
5
5
3
3
5
5
5
5
3
5
5
3
5
5
4
3
5
3
5
5
5
5
3
5
5
5
2
5
3
5
5
5
5
5
5
5
4
4
5
4
5
3
3
2
2
3
3
4
4
3
3
4
4
4
3
4
3
4
3
3
4
4
3
3
3
4
4
4
3
4
4
4
4
2
4
4
4
4
4
4
4
4
4
4
4
3
2
4
3
4
4
4
4
5
4
2
2
4
4
4
4
4
2
4
3
5
4
4
4
4
4
4
4
4
4
4
4
1
3
4
2
4
2
4
4
2
4
1
3
1
2
4
4
4
2
5
4
4
4
4
4
3
3
4
4
4
4
4
4
4
2
4
3
4
4
3
4
4
3
3
3
4
4
4
4
3
5
5
4
4
5
4
4
3
5
5
5
5
5
4
4
4
4
4
4
4
4
4
4
4
5
5
3
5
5
5
5
5
5
4
5
5
5
4
5
5
4
3
3
5
5
4
4
4
4
4
3
4
4
4
4
4
5
3
3
5
5
DM5
C1
3
3
2
4
4
4
3
2
1
1
1
4
1
3
3
3
3
2
4
3
3
3
3
3
3
3
2
4
4
2
2
4
1
3
1
2
4
3
4
4
4
3
4
4
4
3
C2
4
3
3
4
1
4
4
4
1
1
1
5
3
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
4
4
4
2
5
5
4
4
4
4
4
3
5
3
5
4
5
C3
3
3
3
3
1
3
4
4
1
1
1
5
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
4
4
4
2
5
5
3
3
4
4
4
4
5
3
3
4
5
C4
2
2
2
3
1
4
4
5
1
1
1
5
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
1
4
4
4
4
4
4
4
4
5
3
3
3
4
C5
4
2
3
4
1
3
3
3
1
1
1
5
3
3
3
3
4
3
3
3
3
3
3
3
3
3
3
3
2
4
5
4
1
4
4
3
4
3
3
4
4
5
4
3
4
4
L1
4
3
2
5
4
2
3
3
1
1
1
1
2
3
3
3
3
2
4
3
4
3
3
3
3
3
3
4
3
3
2
4
1
4
2
3
4
3
4
4
4
3
3
4
4
4
L2
3
2
3
3
1
4
4
4
1
1
1
4
2
4
4
2
3
4
3
3
3
3
4
3
3
3
3
3
2
3
5
4
1
4
3
3
5
4
3
4
3
4
4
3
5
2
L3
3
3
3
4
1
3
3
2
1
1
1
3
2
3
3
2
3
3
3
3
3
3
3
3
3
3
3
4
1
3
4
3
1
4
3
2
5
4
4
4
3
4
4
2
5
2
4
3
2
3
1
3
2
3
1
1
1
3
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
4
3
1
3
3
2
4
3
4
4
3
4
4
4
5
2
3
3
4
4
3
3
3
5
5
5
3
4
4
3
4
4
3
3
3
4
4
4
4
3
5
5
5
5
5
5
5
5
4
4
4
5
3
1
4
4
4
4
4
4
4
5
5
5
5
5
5
3
4
4
4
3
1
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
5
5
2
2
4
4
4
4
3
3
4
5
5
5
4
5
4
4
5
4
4
3
2
3
3
4
4
4
3
3
5
5
5
4
5
3
3
4
5
3
3
4
4
5
2
2
4
4
3
5
5
5
5
4
3
4
3
5
4
4
3
4
5
4
2
3
4
3
5
5
5
5
4
3
4
3
5
4
4
3
4
4
3
4
3
2
3
5
5
5
4
4
3
4
3
4
4
3
3
2
2
3
3
4
5
3
3
3
3
4
3
3
4
4
2
4
4
4
3
3
4
4
4
3
3
3
1
2
4
4
4
3
3
3
3
3
2
4
4
4
4
5
5
5
5
4
4
4
4
3
5
4
4
2
5
3
3
3
3
3
3
3
3
2
4
4
4
5
5
5
5
5
3
3
3
3
3
3
4
4
2
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
2
4
4
4
3
2
3
3
3
3
2
3
4
3
4
5
5
4
5
3
3
3
4
5
4
4
4
4
4
3
4
4
2
3
3
2
3
3
3
3
3
4
5
4
3
4
3
3
4
4
4
4
4
4
2
3
3
3
4
2
3
4
4
4
4
3
3
4
4
5
4
3
5
3
3
4
4
3
3
4
3
3
4
3
4
4
4
3
4
4
3
4
3
4
4
5
3
4
3
4
4
3
3
4
3
3
4
3
3
3
3
4
3
3
3
3
4
4
4
3
3
4
4
4
4
3
4
3
3
3
4
3
3
4
3
3
3
3
2
2
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
3
3
4
4
5
3
3
4
5
3
3
2
4
4
4
3
2
1
1
1
4
1
3
3
3
3
2
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
5
5
5
5
5
5
5
5
4
5
4
3
3
4
1
4
4
4
1
1
1
5
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
4
4
3
3
3
3
1
3
4
4
1
1
1
5
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
2
2
2
3
1
4
4
5
1
1
1
5
2
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
4
4
4
2
3
4
1
3
3
3
1
1
1
5
3
3
3
3
4
3
3
4
4
4
2
4
4
4
4
3
4
4
4
4
4
4
4
5
3
4
4
3
4
3
5
3
5
5
4
4
3
2
5
4
2
3
3
1
1
1
1
2
3
3
3
3
2
4
4
3
3
5
4
4
4
3
4
4
4
4
4
4
4
4
4
3
4
4
4
4
4
5
3
4
4
5
3
2
3
3
1
4
4
4
1
1
1
4
2
4
4
2
3
4
4
4
3
2
4
4
5
4
3
4
4
4
4
4
4
3
3
4
4
4
4
4
4
4
5
4
4
4
5
3
3
3
4
1
3
3
2
1
1
1
3
2
3
3
2
3
3
4
4
3
3
4
4
4
4
3
4
4
4
4
4
4
4
3
5
3
5
4
4
4
3
5
2
4
4
5
4
3
2
3
1
3
2
3
1
1
1
3
2
3
3
3
3
3
4
3
3
3
3
3
3
3
2
4
4
2
2
4
1
3
1
2
4
3
4
4
4
3
4
4
4
3
3
3
4
4
3
3
3
5
5
5
3
4
4
3
4
4
3
3
3
4
3
3
3
3
3
3
3
3
3
3
4
4
4
2
5
5
4
4
4
4
4
3
5
3
5
4
5
4
4
4
4
3
5
5
5
5
5
5
5
5
4
4
4
5
3
1
3
3
3
3
3
3
3
3
3
3
2
4
4
4
2
5
5
3
3
4
4
4
4
5
3
3
4
5
4
4
4
4
4
4
4
5
5
5
5
5
5
3
4
4
4
3
1
3
3
3
3
3
3
3
3
3
3
3
3
3
3
1
4
4
4
4
4
4
4
4
5
3
3
3
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
5
5
2
2
3
3
3
3
3
3
3
3
3
3
2
4
5
4
1
4
4
3
4
3
3
4
4
5
4
3
4
4
4
4
4
4
3
3
4
5
5
5
4
5
4
4
5
4
4
3
2
4
3
4
3
3
3
3
3
3
4
3
3
2
4
1
4
2
3
4
3
4
4
4
3
3
4
4
4
3
3
4
4
4
3
3
5
5
5
4
5
3
3
4
5
3
3
4
3
3
3
3
4
3
3
3
3
3
2
3
5
4
1
4
3
3
5
4
3
4
3
4
4
3
5
2
4
5
2
2
4
4
3
5
5
5
5
4
3
4
3
5
4
4
3
3
3
3
3
3
3
3
3
3
4
1
3
4
3
1
4
3
2
5
4
4
4
3
4
4
2
5
2
4
5
4
2
3
4
3
5
5
5
5
4
3
4
3
5
4
4
3
3
3
3
3
3
3
3
3
3
3
2
3
4
3
1
3
3
2
4
3
4
4
3
4
4
4
5
2
4
4
3
4
3
2
3
5
5
5
4
4
3
4
3
4
4
3
3
2
2
3
3
4
5
3
3
3
3
4
3
3
4
4
2
4
4
4
3
3
4
4
4
3
3
3
3
3
3
2
2
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
1
2
4
4
4
3
3
3
3
3
2
4
4
4
4
5
5
5
5
4
4
4
4
3
5
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
5
2
5
3
3
3
3
3
3
3
3
2
4
4
4
5
5
5
5
5
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
2
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
2
4
4
4
3
2
3
3
3
3
2
3
4
3
4
5
5
4
5
3
3
3
4
5
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
4
4
2
3
3
2
3
3
3
3
3
4
5
4
3
4
3
3
4
4
4
4
4
4
3
4
4
4
2
4
4
4
4
3
4
4
4
4
4
4
4
5
3
4
2
3
3
3
4
2
3
4
4
4
4
3
3
4
4
5
4
3
5
3
3
4
4
3
3
4
3
4
4
3
3
5
4
4
4
3
4
4
4
4
4
4
4
4
4
3
4
3
4
3
4
4
4
3
4
4
3
4
3
4
4
5
3
4
3
4
4
3
3
4
3
3
4
3
4
4
3
2
4
4
5
4
3
4
4
4
4
4
4
3
3
4
4
4
3
3
3
4
3
3
3
3
4
4
4
3
3
4
4
4
4
3
4
3
3
3
4
3
3
4
3
4
4
3
3
4
4
4
4
3
4
4
4
4
4
4
4
3
5
3
5
3
3
4
4
5
3
3
4
5
3
3
2
4
4
4
3
2
1
1
1
4
1
3
3
3
3
2
4
3
3
3
3
3
3
3
2
4
4
2
2
4
1
3
1
2
4
3
5
5
5
5
5
5
5
4
5
4
3
3
4
1
4
4
4
1
1
1
5
3
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
4
4
4
2
5
5
4
4
4
4
4
4
4
5
5
5
4
4
3
3
3
3
1
3
4
4
1
1
1
5
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
4
4
4
2
5
5
3
3
4
4
4
4
4
5
5
5
5
5
2
2
2
3
1
4
4
5
1
1
1
5
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
1
4
4
4
4
4
4
4
4
4
5
5
5
4
4
4
2
3
4
1
3
3
3
1
1
1
5
3
3
3
3
4
3
3
3
3
3
3
3
3
3
3
3
2
4
5
4
1
4
4
3
4
3
4
3
4
3
5
3
5
5
4
4
3
2
5
4
2
3
3
1
1
1
1
2
3
3
3
3
2
4
3
4
3
3
3
3
3
3
4
3
3
2
4
1
4
2
3
4
3
4
4
4
4
5
3
4
4
5
3
2
3
3
1
4
4
4
1
1
1
4
2
4
4
2
3
4
3
3
3
3
4
3
3
3
3
3
2
3
5
4
1
4
3
3
5
4
4
4
4
4
5
4
4
4
5
3
3
3
4
1
3
3
2
1
1
1
3
2
3
3
2
3
3
3
3
3
3
3
3
3
3
3
4
1
3
4
3
1
4
3
2
5
4
4
4
4
3
5
2
4
4
5
4
3
2
3
1
3
2
3
1
1
1
3
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
4
3
1
3
3
2
4
3
4
4
4
3
4
4
4
3
3
3
4
4
3
3
3
5
5
5
3
4
4
3
4
4
3
3
3
2
2
3
3
4
5
3
3
3
3
4
3
3
4
4
2
4
4
4
3
4
4
3
5
3
5
4
5
4
4
4
4
3
5
5
5
5
5
5
5
5
4
4
4
5
3
1
1
2
4
4
4
3
3
3
3
3
2
4
4
4
4
5
5
5
5
4
4
4
4
5
3
3
4
5
4
4
4
4
4
4
4
5
5
5
5
5
5
3
4
4
4
3
1
2
5
3
3
3
3
3
3
3
3
2
4
4
4
5
5
5
5
5
3
4
4
4
5
3
3
3
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
5
5
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
3
4
4
5
4
3
4
4
4
4
4
4
3
3
4
5
5
5
4
5
4
4
5
4
4
3
2
2
4
4
4
3
2
3
3
3
3
2
3
4
3
4
5
5
4
5
3
4
4
4
3
3
4
4
4
3
3
4
4
4
3
3
5
5
5
4
5
3
3
4
5
3
3
4
4
4
3
4
4
2
3
3
2
3
3
3
3
3
4
5
4
3
4
3
3
4
3
4
4
3
5
2
4
5
2
2
4
4
3
5
5
5
5
4
3
4
3
5
4
4
3
2
3
3
3
4
2
3
4
4
4
4
3
3
4
4
5
4
3
5
3
4
4
3
4
4
2
5
2
4
5
4
2
3
4
3
5
5
5
5
4
3
4
3
5
4
4
3
3
4
3
4
4
4
3
4
4
3
4
3
4
4
5
3
4
3
4
4
4
4
3
4
4
4
5
2
4
4
3
4
3
2
3
5
5
5
4
4
3
4
3
4
4
3
3
3
3
3
4
3
3
3
3
4
4
4
3
3
4
4
4
4
3
4
3
3
4
4
4
3
3
3
3
3
3
2
2
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
3
3
4
4
5
3
3
4
5
3
3
2
4
4
4
3
2
1
1
1
4
4
4
3
5
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
5
5
5
5
5
5
5
5
4
5
4
3
3
4
1
4
4
4
1
1
1
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
4
4
3
3
3
3
1
3
4
4
1
1
1
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
2
2
2
3
1
4
4
5
1
1
1
3
3
4
5
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
4
4
4
2
3
4
1
3
3
3
1
1
1
3
4
4
4
4
4
4
3
4
4
4
2
4
4
4
4
3
4
4
4
4
4
4
4
5
3
4
4
3
4
3
5
3
5
5
4
4
3
2
5
4
2
3
3
1
1
1
3
4
4
3
3
4
3
4
4
3
3
5
4
4
4
3
4
4
4
4
4
4
4
4
4
3
4
4
4
4
4
5
3
4
4
5
3
2
3
3
1
4
4
4
1
1
1
3
3
4
3
3
4
3
4
4
3
2
4
4
5
4
3
4
4
4
4
4
4
3
3
4
4
4
4
4
4
4
5
4
4
4
5
3
3
3
4
1
3
3
2
1
1
1
3
3
4
3
3
4
3
4
4
3
3
4
4
4
4
3
4
4
4
4
4
4
4
3
5
3
5
4
4
4
3
5
2
4
4
5
4
3
2
3
1
3
2
3
1
1
1
4
1
3
3
3
3
2
4
3
3
3
3
3
3
3
2
4
4
2
2
4
1
3
1
2
4
3
4
4
4
3
4
4
4
3
3
3
4
4
3
3
3
5
5
5
3
4
5
3
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
4
4
4
2
5
5
4
4
4
4
4
3
5
3
5
4
5
4
4
4
4
3
5
5
5
5
5
5
5
5
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
4
4
4
2
5
5
3
3
4
4
4
4
5
3
3
4
5
4
4
4
4
4
4
4
5
5
5
5
5
5
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
1
4
4
4
4
4
4
4
4
5
3
3
3
4
4
4
4
4
4
4
4
5
5
5
5
5
5
3
3
3
3
4
3
3
3
3
3
3
3
3
3
3
3
2
4
5
4
1
4
4
3
4
3
3
4
4
5
4
3
4
4
4
4
4
4
3
3
4
5
5
5
4
5
1
2
3
3
3
3
2
4
3
4
3
3
3
3
3
3
4
3
3
2
4
1
4
2
3
4
3
4
4
4
3
3
4
4
4
3
3
4
4
4
3
3
5
5
5
4
5
4
2
4
4
2
3
4
3
3
3
3
4
3
3
3
3
3
2
3
5
4
1
4
3
3
5
4
3
4
3
4
4
3
5
2
4
5
2
2
4
4
3
5
5
5
5
4
3
2
3
3
2
3
3
3
3
3
3
3
3
3
3
3
4
1
3
4
3
1
4
3
2
5
4
4
4
3
4
4
2
5
2
4
5
4
2
3
4
3
5
5
5
5
4
3
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
4
3
1
3
3
2
4
3
4
4
3
4
4
4
5
2
4
4
3
4
3
2
3
5
5
5
4
4
4
3
4
4
3
3
3
2
2
3
3
4
5
3
3
3
3
4
3
3
4
4
2
4
4
4
3
3
4
4
4
3
3
3
3
3
3
2
2
4
4
4
4
4
4
4
4
5
4
4
4
5
3
1
1
2
4
4
4
3
3
3
3
3
2
4
4
4
4
5
5
5
5
4
4
4
4
3
5
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
3
4
4
4
3
1
2
5
3
3
3
3
3
3
3
3
2
4
4
4
5
5
5
5
5
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
4
4
3
2
2
4
4
4
3
2
3
3
3
3
2
3
4
3
4
5
5
4
5
3
3
3
4
5
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
3
4
5
3
3
4
4
4
3
4
4
2
3
3
2
3
3
3
3
3
4
5
4
3
4
3
3
4
4
4
4
4
4
3
4
4
4
2
4
4
4
4
3
4
4
4
3
4
3
5
4
4
3
2
3
3
3
4
2
3
4
4
4
4
3
3
4
4
5
4
3
5
3
3
4
4
3
3
4
3
4
4
3
3
5
4
4
4
3
4
4
4
4
3
4
3
5
4
4
3
3
4
3
4
4
4
3
4
4
3
4
3
4
4
5
3
4
3
4
4
3
3
4
3
3
4
3
4
4
3
2
4
4
5
4
3
4
4
4
4
3
4
3
4
4
3
3
3
3
3
4
3
3
3
3
4
4
4
3
3
4
4
4
4
3
4
3
3
3
4
3
3
4
3
4
4
3
3
4
4
4
4
3
4
4
4
4
4
4
4
4
4
4
3
3
3
4
4
5
3
3
4
5
4
4
4
4
4
3
5
5
5
5
5
5
5
5
4
5
4
4
4
4
4
4
4
4
4
4
4
5
5
5
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
4
4
4
4
4
4
4
4
4
4
4
5
5
5
4
4
4
4
4
4
5
3
4
4
3
4
3
5
3
5
5
4
4
4
4
4
4
3
4
4
4
4
4
5
3
4
4
5
4
4
3
3
4
4
4
4
4
4
4
5
4
4
4
5
4
4
4
3
5
3
5
4
4
4
3
5
2
4
4
5
L4
L5
2
1
3
3
1
4
2
4
1
1
1
3
2
3
3
2
2
3
3
3
3
3
2
3
3
3
3
3
2
4
3
3
1
3
2